1,1

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.

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

Eric Weisstein's World of Mathematics, Hamiltonian Path

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.

# A Python function that calculates A091299[n] from Janez Brank. (Replace leading dots by spaces!)

.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)

Equals A006069 + A006070. Divide by 2^n to get A003043. Cf. A003042, A066037, A091302.

Adjacent sequences: A091296 A091297 A091298 this_sequence A091300 A091301 A091302

Sequence in context: A009817 A124105 A079613 this_sequence A007314 A102099 A012298

nonn,more

N. J. A. Sloane (njas(AT)research.att.com), Feb 20 2004

a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005