Gray codes...

[Gordon Royle]

I have some questions and comments about Gray codes and the 
corresponding entries in OEIS.

Recall that a Gray code is an enumeration of all 2^n binary words of 
length n such that between any two successive entries only a single bit 
is altered.

Question 1: Is it required that the first and last words also differ by 
a single bit? I have seen the phrase "cyclic Gray code" used to specify 
that this must be true, but I don't know if "Gray code" by itself is 
normally taken to have this property?

Anyway, given a (cyclic) Gray code, we can obviously find a Hamilton 
cycle in the n-cube, and conversely and so these two objects are the 
same.

The raw numbers of Hamilton cycles are listed as A006069

http://www.research.att.com/projects/OEIS?Anum=A006069

which says 2, 8, 96, 43008, 58018928640.  This is a bit odd b/c I 
wouldn't normally consider the 1-cube to have *any* hamilton cycles, 
but it is clear what it means so we won't worry about that.


I call these "raw" numbers because cyclic rearrangements and reversals 
are all counted separately, whereas we would normally count these as 
the same hamilton cycle. If we divide by the appropriate number (2 x 
2^n for n>1) then we get the numbers of distinct hamilton cycles to be

1, 1, 6,1344,90654760

which is *almost* the sequence A066037

http://www.research.att.com/projects/OEIS?Anum=A066037

except that the latter sequence has 0 for the first entry.

Comment: Both sequences are described as "hamiltonian cycles in the 
n-cube", but surely there should be some warning that they are counting 
different things..

Comment: The sequence A066037 also has "number of cyclic n-bit gray 
codes" as an alternative description. But there definitely IS a 1-bit 
gray code under any interpretation, although whether or not there is a 
hamiltonian cycle is (as explained above) questionable.

However this sequence is still not the one that we are really after 
when counting Gray codes because (as stated in the entry) these numbers 
are all divisible by n!/2 because each hamilton cycle generates a 
permutation of {1...n} according to the bits that are flipped first. So 
when counting Gray codes we may as well assume that the bits are first 
flipped in counting order, and then multiply the result if we want to.

Doing this gives a sequence that is not in the OEIS as far as I can 
see..

If we consider Gray codes that are not necessarily cyclic, then these 
correspond to hamiltonian paths in the n-cube. The numbers of these are 
given in the sequence A006070.

http://www.research.att.com/projects/OEIS?Anum=A006070

But this is a bit odd ... it gives 0 as the number for n=1 and n=2. 
Obviously this is meant to be counting "hamilton paths which do not 
complete to hamilton cycles" but this condition is normally not implied 
by the phrase "hamilton path" (is it?). At the very least, maybe a 
warning should be inserted.

Also a small comment... I always thought that the correct phrase was 
"Hamilton cycle" or "Hamilton path" and that the adverb form 
"hamiltonian" is only used when saying that the graph itself is 
"hamiltonian". Saying "hamiltonian path" seems odd... anybody else 
agree (or disagree)?


All the best

Gordon






-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 3335 bytes
Desc: not available
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20040218/e10b15db/attachment.bin>