login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066037 Number of Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes. 10
1, 1, 6, 1344, 906545760, 35838213722570883870720 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..6.

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, 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 n-cube, Discrete Mathematics, 17 (1977), 143-146.

Harri Haanpaa and P. R. J. Ostergard, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.

Harary, Hayes, and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 277-289.

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Eric Weisstein's World of Mathematics, Hypercube Graph

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 11:33 EST 2019. Contains 319271 sequences. (Running on oeis4.)