cp's OEIS Frontend

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

%I A091299 #32 Feb 16 2025 08:32:52
%S A091299 2,8,144,91392,187499658240
%N A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.
%C A091299 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.
%D A091299 M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
%H A091299 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>
%H A091299 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%e A091299 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.
%o A091299 (Python)
%o A091299 # A function that calculates A091299[n] from Janez Brank.
%o A091299 def CountGray(n):
%o A091299     def Recurse(unused, lastVal, nextSet):
%o A091299         count = 0
%o A091299         for changedBit in range(0, min(nextSet + 1, n)):
%o A091299             newVal = lastVal ^ (1 << changedBit)
%o A091299             mask = 1 << newVal
%o A091299             if unused & mask:
%o A091299                 if unused == mask:
%o A091299                     count += 1
%o A091299                 else:
%o A091299                     count += Recurse(
%o A091299                         unused & ~mask, newVal, max(nextSet, changedBit + 1)
%o A091299                     )
%o A091299         return count
%o A091299     count = Recurse((1 << (1 << n)) - 2, 0, 0)
%o A091299     for i in range(1, n + 1):
%o A091299         count *= 2 * i
%o A091299     return max(1, count)
%o A091299 [CountGray(n) for n in range(1, 4)]
%Y A091299 Equals A006069 + A006070. Divide by 2^n to get A003043.
%Y A091299 Cf. A003042, A066037, A091302, A284673.
%K A091299 nonn,hard,more
%O A091299 1,1
%A A091299 _N. J. A. Sloane_, Feb 20 2004
%E A091299 a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005