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
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
More information about the SeqFan
mailing list