counting problem...

[Gordon Royle]

Hi seqfans..

Here is a counting problem that arises naturally when playing with Gray 
codes, as I have been doing recently.

Recall that a (cyclic) Gray code is a listing of the binary n-tuples in 
a cyclic sequence so that adjacent elements differ in exactly one bit 
position. This means that we could describe a Gray code just by listing 
the bit that gets changed at each step (rather than the entire 
n-tuple). This gives us a sequence of 2^n numbers, each of which lies 
in {0..n-1}.

Now count up the number of times c_i that the bit in position i is 
changed. This gives us a  sequence (c0,c1,...,c_{n-1}), called the 
transition counts of the code, such that

	- each number is even, and
	- the sum is 2^n

In addition, if we assume that we re-order everything so that these 
numbers are non-decreasing (c_0 <= c_1 <= ... <= c_{n-1}) then there is 
an additional condition

	c_0 + c_1 + ... + c_{j-1} >= 2^j

by noting that all 2^j patterns must occur in the j least-flipped bit 
positions.

For example, for n=4 there are 4 possible sequences satisfying these 
conditions:

	2 2 4 8
	2 2 6 6
	2 4 4 6
	4 4 4 4

and indeed there are cyclic Gray codes with each possible transition 
count sequence.


My computations (not yet thoroughly checked) show that the number of 
possibilities is

	1 1 1 4 28 550 28456 4134861

This is not in OEIS and superseeker did not help, but it seems like the 
sort of problem that should be solvable theoretically.....

Can anyone help with this one?

Gordon