# counting problem...

Gordon Royle gordon at csse.uwa.edu.au
Fri Mar 12 10:10:47 CET 2004

```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

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

```