A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.

2, 8, 144, 91392, 187499658240

Offset: 1

Author

N. J. A. Sloane, Feb 20 2004

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.

Examples

			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.
		

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

Crossrefs

Equals A006069 + A006070. Divide by 2^n to get A003043.

Cf. A003042, A066037, A091302, A284673.

Programs

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

Extensions

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