A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

1, 2, 12, 2688, 1813091520, 71676427445141767741440

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

Finding a(6) is Problem 43 in the Knuth reference.

References

• Martin Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
• Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• 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]
• Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
• John Jungck, Genetic Codes as Codes: Towards a Theoretical Basis for Bioinformatics, International Symposium on Mathematical and Computational Biology (BIOMAT 2008), see p. 19.
• Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the n-bit Gray codes by restricted random generation of permutations of 1 to 2^n, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901.
• Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
• Vladimir Shevelev, Combinatorial minors of matrix functions and their applications
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, Hypercube Graph

Crossrefs

Equals A006069 divided by 2^n.

Cf. A006070, A091299, A003043, A091302, A066037, A159344, A180026.

Formula

a(n) = 2 * A066037(n).

Extensions

a(6) from Michel Deza, Mar 28 2010

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