Two ordering problems

[David Wilson]

Max Alekseyev wrote:
> 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
>
>   
Your observation is certainly a property of good sequences, indeed the 
distance between any two adjacent X's will always be k or k+1 for some k 
(similarly for adjacent Y's). This is necessary for a good sequence, but 
not sufficient. For example

X,Y,X,Y,X,Y,X,X,Y,X,X

is not good.