Two ordering problems
David Wilson
dwilson at gambitcomm.com
Tue Aug 26 15:39:35 CEST 2008
Problem 1:
Let X = { x >= 0: x == a (mod b) }, Y = { y >= 0; y == c (mod d) }be
disjoint.
For example, X = { x : x == 0 (mod 4) }, Y = { y : y == 1 (mod 6) }
The union of these two sets is
0,1,4,7,8,12,13,16,19,20,24,25,...
Which are in the sets
X,Y,X,Y,X,X,Y,X,Y,X,X,Y,...
Let any finite prefix of this sequence be a "good" sequence, so that
(), (X), (X,Y), (X,Y,X), ...
are good.
Some sequences are not good for any choice of X and Y, such as
(X,Y,Y,Y,X,Y,X)
Over all possible X and Y, how many good sequences of length n are there?
Problem 2:
Let p1 < p2 < ... < p_n be primes (call p1 = p, p2 = q, p3 = r, ...)
Consider the set M of divisors of p1*p2*...*p_n. How many ways can M be
ordered?
For n = 0, we have m = { 1 }, with 1 ordering.
For n = 1, we have M = { 1, p }. There is 1 possible ordering, 1 < p.
For n = 2, we have M = { 1, p, q, pq }. Remembering p < q, there is
again 1 possible ordering, 1 < p < q < pq.
For n = 3, we have M = { 1, p, q, r, pq, pr, qr, pqr }. There are 2
possible orderings here
1 < p < q < r < pq < pr < qr < pqr
1 < p < q < pq < r < pr < qr < pqr
How many possible orderings are there for larger n?
Dear Seqfans
I noticed that our public machines were unavailable
yesterday at certain times, and the same thing seems to be happening today
I've reported the problem.
Neil
More information about the SeqFan
mailing list