The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066037 Number of (undirected) 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)



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.


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 Patric R. J. Östergård, 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


The 2-cube has a single cycle consisting of all 4 edges.


Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* Eric W. Weisstein, Apr 01 2017 *)


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 A307871 A195646

Adjacent sequences:  A066034 A066035 A066036 * A066038 A066039 A066040




John Tromp, Dec 12 2001


a(6) from Michel Deza, Mar 28 2010

a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012

Name clarified by Eric W. Weisstein, May 06 2019



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 November 29 21:32 EST 2021. Contains 349416 sequences. (Running on oeis4.)