|
| |
|
|
A066037
|
|
Number of Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.
|
|
7
| | |
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| This is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one and the last node is adjacent to the first; and then dividing the total by 2^(n+1) because the starting node and the direction do not really matter.
The number is a multiple of n!/2 since any directed cycle starting from 0^n induces a permutation on the n bits, namely the order in which they first get set to 1.
|
|
|
REFERENCES
| R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.
Harary, Hayes and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 7-289.
|
|
|
EXAMPLE
| The 2-cube has a single cycle consisting of all 4 edges.
|
|
|
CROSSREFS
| Equals A006069/2^(n+1) and A003042/2.
Cf. A006070, A091299, A003043, A091302.
Sequence in context: A055306 A203331 A172625 * A195646 A199645 A107252
Adjacent sequences: A066034 A066035 A066036 * A066038 A066039 A066040
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| John Tromp (tromp(AT)cwi.nl), Dec 12 2001
|
|
|
EXTENSIONS
| a(6) from Michel Deza, Mar 28 2010
|
| |
|
|
