Two ordering problems

[Max Alekseyev]

On Tue, Aug 26, 2008 at 6:39 AM, David Wilson <dwilson at gambitcomm.com> wrote:
> 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?

It appears that the sequence is good iff the number of Y (resp. X)
symbols between any two neighboring X (resp. Y) symbols either equals
an integer constant or varies between some two consecutive integer
values.
In the aforementioned sample sequence
X,Y,X,Y,X,X,Y,X,Y,X,X,Y,...
the distance between every two neighboring X's is 0 or 1 and the
distance between every two neighboring Y's is 1 or 2.

With this characterization in mind, it is easy to compute the number
of good sequences of length n.

Regards,
Max