gray codes

[N. J. A. Sloane]

Gordon:

i checked the M Gardner reference

here is what he has:

n   Hamiltonian circuits  Hamiltonian (noncyclic) paths
-------------------------------------------------------
1            2                      0
2            8                      0
3           96                     48
4        43008                  48384

      (A006069)             (A006070)

 From reading the previous page, I think the next term in the
first sequence is

5    5859364320

so (apart from the dubious a(1) = 2) A006069 is correct.
And the description should be:

Number of Hamiltonian circuits on the n-cube,
where a circuit is specified by an ordered list of the
2^n vertices (the last node being
adjacent to the first), and has a distinguished starting node
and a direction.
So for n = 2 there are 8 possibilities.
And I get 96 for n=3, too.

I now think the second sequence, A006070, counts paths which
start anywhere, are directed, and end at a node that
is NOT adjacent to the starting node
That explains the two 0 values.

So these are strictly non-circuit paths which
visit every node.  And I think 48 is correct for n=3. There
you have to end at a node that is diametrically opposite
the start.

According to Gardner, if i am interpreting his
article correctly, the 5-th term in the second sequence should be
187499658240 -  5859364320 = 181640293920

so that will fix A006070.


Dividing A006069 by 2^(n+1) we get A066037, as you noticed.  That seems
the canonical version of the sequence.


But it seems to me there should be a third sequence,
the sum of A006069 and A006070

This is the total number of Ham paths, without a restriction on
where they end.
So I will add that one.

Gordon, you also said:

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

Am i right in thinking this is the sequence

0  1  2  1344/12 = 112  906545760/60 = 15109096 ?

I will add that one too - but please tell me how you
would like it described.


Thanks for starting this discussion!

I think I understand Gardner's value of 2 in 1 dim.

he thinks of the Ham cycle as a list of 2^n numbers

so he would say:  12  or  21

hence A006069(1) = 2

Neil