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

2, 8, 144, 91392, 187499658240

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

Table of n, a(n) for n=1..5.

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

# A Python 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

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

Cf. A003042, A066037, A091302, A284673.

Sequence in context: A009817 A124105 A079613 * A362729 A307326 A007314

Adjacent sequences: A091296 A091297 A091298 * A091300 A091301 A091302

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