This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006069 Number of directed Hamiltonian cycles (or Gray codes) on n-cube with a marked starting node.
(Formerly M1903)
2, 8, 96, 43008, 58018928640, 4587291356489073135452160 (list; graph; refs; listen; history; text; internal format)



More precisely, 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.


M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


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

H. Haanpaa and P. R. J. Ostergard, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995. doi:S0025-5718-2013-02741-X

D. Sensarma, S. S. Sarma, GMDES: A graph based modified Data Encryption Standard algorithm with enhanced security, IJRET: International Journal of Research in Engineering and Technology 03:03 (2014), 653-660. See Section 2.2.

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391v1 [There may be errors - see Haanpaa and Ostergard, 2012]

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Eric Weisstein's World of Mathematics, Hypercube Graph


a(n)=A003042(n)*2^n. - Max Alekseyev, Jun 15 2006


a(1) = 2: we have 1,2 or 2,1.

a(2) = 8: label the nodes 1, 2, ..., 4. Then the 8 possibilities are 1,2,3,4; 1,4,3,2; 2,3,4,1; 2,1,4,3; etc.


Cf. A003042, A006070, A091299, A091302, A159344.

Sequence in context: A001417 A156926 A001697 * A270485 A223042 A052457

Adjacent sequences:  A006066 A006067 A006068 * A006070 A006071 A006072




N. J. A. Sloane.


a(5) corrected by Jonathan Cross (jcross(AT)wcox.com), Oct 10 2001

Definition corrected by Max Alekseyev, Jun 15 2006

a(6) from Michel Deza, Mar 28 2010

a(6) corrected by Haanpaa and Ostergard, 2012. - N. J. A. Sloane, Sep 06 2012



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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 17 14:12 EST 2018. Contains 299296 sequences. (Running on oeis4.)