

A066037


Number of Hamiltonian cycles in the binary ncube, or the number of cyclic nbit Gray codes.


10




OFFSET

1,3


COMMENTS

This is the number of ways of making a list of the 2^n nodes of the ncube, 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

Table of n, a(n) for n=1..6.
Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6cube, arXiv:1003.4391 [cs.DM], 2010. [There may be errors  see Haanpaa and Ostergard, 2012]
R. J. Douglas, Bounds on the number of Hamiltonian circuits in the ncube, Discrete Mathematics, 17 (1977), 143146.
Harri Haanpaa and P. R. J. Ostergard, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979995.
Harary, Hayes, and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 277289.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph


EXAMPLE

The 2cube 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

Equals A006069/2^(n+1) and A003042/2.
Cf. A006070, A091299, A003043, A091302.
Cf. A236602 (superset).  Stanislav Sykora, Feb 01 2014
Sequence in context: A055306 A203331 A172625 * A279924 A195646 A265473
Adjacent sequences: A066034 A066035 A066036 * A066038 A066039 A066040


KEYWORD

nonn,nice,more


AUTHOR

John Tromp, Dec 12 2001


EXTENSIONS

a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Ostergard, 2012.  N. J. A. Sloane, Sep 06 2012


STATUS

approved



