The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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)

%I M1903

%S 2,8,96,43008,58018928640,4587291356489073135452160

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

%C 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.

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

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

%H H. Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995. doi:<a href="http://dx.doi.org/10.1090/S0025-5718-2013-02741-X">S0025-5718-2013-02741-X</a>

%H D. Sensarma, S. S. Sarma, <a href="http://ijret.org/Volumes/V03/I03/IJRET_110303121.pdf">GMDES: A graph based modified Data Encryption Standard algorithm with enhanced security</a>, IJRET: International Journal of Research in Engineering and Technology 03:03 (2014), 653-660. See Section 2.2.

%H Michel Deza and Roman Shklyar, <a href="http://arxiv.org/abs/1003.4391">Enumeration of Hamiltonian Cycles in 6-cube</a>, arXiv:1003.4391v1 [There may be errors - see Haanpaa and Ostergard, 2012]

%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>

%F a(n) = A003042(n)*2^n. - _Max Alekseyev_, Jun 15 2006

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

%e 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.

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

%K nonn,more

%O 1,1

%A _N. J. A. Sloane_.

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

%E Definition corrected by _Max Alekseyev_, Jun 15 2006

%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

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 June 4 06:41 EDT 2020. Contains 334822 sequences. (Running on oeis4.)