A003043 Number of Hamiltonian paths (or Gray codes) on n-cube with a marked starting node.

1, 2, 18, 5712, 5859364320

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• 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. The final node may or may not be adjacent to the first. Finally, divide by 2^n since the starting node really doesn't matter.

Also, the number of strings s of length 2^n - 1 over the alphabet {1,2,...,n} with the property that every contiguous subblock has some letter that appears an odd number of times.

References

• M. Gardner, Mathematical Games, Sci. Amer. Vol. 228 (No. 4, Apr. 1973), p. 111.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• 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, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).

Crossrefs

Cf. A091299, A006069, A006070, A003042, A066037, A091302, A179926.

Formula

a(n) = A091299(n)/2^n.

Extensions

a(5) (from A091299) from Max Alekseyev, Jul 09 2006

Alternative description added by Jeffrey Shallit, Feb 02 2013