OFFSET
1,1
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.
REFERENCES
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
LINKS
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph
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,3,4,2; 2,3,4,1; 2,1,4,3; etc.
PROG
(Python)
# A function that calculates A091299[n] from Janez Brank.
def CountGray(n):
def Recurse(unused, lastVal, nextSet):
count = 0
for changedBit in range(0, min(nextSet + 1, n)):
newVal = lastVal ^ (1 << changedBit)
mask = 1 << newVal
if unused & mask:
if unused == mask:
count += 1
else:
count += Recurse(
unused & ~mask, newVal, max(nextSet, changedBit + 1)
)
return count
count = Recurse((1 << (1 << n)) - 2, 0, 0)
for i in range(1, n + 1):
count *= 2 * i
return max(1, count)
[CountGray(n) for n in range(1, 4)]
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
N. J. A. Sloane, Feb 20 2004
EXTENSIONS
a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005
STATUS
approved