|
%I #43 Feb 02 2020 21:28:52
%S 1,1,6,1344,906545760,35838213722570883870720
%N Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.
%C 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.
%C 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.
%H Michel Deza and Roman Shklyar, <a href="http://arxiv.org/abs/1003.4391">Enumeration of Hamiltonian Cycles in 6-cube</a>, arXiv:1003.4391 [cs.DM], 2010. [There may be errors - see Haanpaa and Ostergard, 2012]
%H R. J. Douglas, <a href="http://dx.doi.org/10.1016/0012-365X(77)90143-1">Bounds on the number of Hamiltonian circuits in the n-cube</a>, Discrete Mathematics, 17 (1977), 143-146.
%H Harri Haanpaa and Patric R. J. Östergård, <a href="https://doi.org/10.1090/S0025-5718-2013-02741-X">Counting Hamiltonian cycles in bipartite graphs</a>, Math. Comp. 83 (2014), 979-995.
%H Harary, Hayes, and Wu, <a href="http://dx.doi.org/10.1016/0898-1221(88)90213-1">A survey of the theory of hypercube graphs</a>, Computers and Mathematics with Applications, 15(4), 1988, 277-289.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%e The 2-cube has a single cycle consisting of all 4 edges.
%t Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* _Eric W. Weisstein_, Apr 01 2017 *)
%Y Equals A006069/2^(n+1) and A003042/2.
%Y Cf. A006070, A091299, A003043, A091302.
%Y Cf. A236602 (superset). - _Stanislav Sykora_, Feb 01 2014
%K nonn,nice,more
%O 1,3
%A _John Tromp_, Dec 12 2001
%E a(6) from Michel Deza, Mar 28 2010
%E a(6) corrected by Haanpaa and Östergård, 2012. - _N. J. A. Sloane_, Sep 06 2012
%E Name clarified by _Eric W. Weisstein_, May 06 2019
| 