A006069 Number of directed Hamiltonian cycles (or Gray codes) on n-cube with a marked starting node.

2, 8, 96, 43008, 58018928640, 4587291356489073135452160

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

Comments

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.

Examples

			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.
		

References

• 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).

Links

• H. Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
• 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]
• 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.
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, Hypercube Graph

Crossrefs

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

Formula

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

Extensions

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 Östergård, 2012. - N. J. A. Sloane, Sep 06 2012