

A006069


Number of directed Hamiltonian cycles (or Gray codes) on ncube with a marked starting node.
(Formerly M1903)


9




OFFSET

1,1


COMMENTS

More precisely, this is the number of ways of making a list of the 2^n nodes of the ncube, 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.


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

Table of n, a(n) for n=1..6.
H. Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979995.
Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6cube, 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), 653660. See Section 2.2.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph


FORMULA

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


EXAMPLE

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.


CROSSREFS

Cf. A003042, A006070, A091299, A091302, A159344.
Sequence in context: A156926 A326866 A001697 * A270485 A223042 A052457
Adjacent sequences: A006066 A006067 A006068 * A006070 A006071 A006072


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane.


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


STATUS

approved



