|
|
A066037
|
|
Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.
|
|
10
|
|
|
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
The 2-cube has a single cycle consisting of all 4 edges.
|
|
MATHEMATICA
|
Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* Eric W. Weisstein, Apr 01 2017 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012
|
|
STATUS
|
approved
|
|
|
|