Two ordering problems

[David Wilson]

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