Search: id:A091299
Results 1-1 of 1 results found.

%I A091299
%S A091299 2,8,144,91392,187499658240
%N A091299 Number of Hamiltonian paths (or Gray codes) on 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="http://mathworld.wolfram.com/
               HamiltonianPath.html">Hamiltonian Path</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 # A Python function that calculates A091299[n] from Janez Brank. (Replace 
               leading dots by spaces!)
%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: count += 1
%o A091299 ........ else: count += Recurse(unused & ~mask, newVal,
%o A091299 ............................... max(nextSet, changedBit + 1))
%o A091299 .... return count
%o A091299 .. count = Recurse((1 << (1 << n)) - 2, 0, 0)
%o A091299 .. for i in range(1, n + 1): count *= 2 * i
%o A091299 .. return max(1, count)
%Y A091299 Equals A006069 + A006070. Divide by 2^n to get A003043. Cf. A003042, 
               A066037, A091302.
%Y A091299 Sequence in context: A009817 A124105 A079613 this_sequence A007314 A102099 
               A012298
%Y A091299 Adjacent sequences: A091296 A091297 A091298 this_sequence A091300 A091301 
               A091302
%K A091299 nonn,more
%O A091299 1,1
%A A091299 N. J. A. Sloane (njas(AT)research.att.com), Feb 20 2004
%E A091299 a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005

Search completed in 0.002 seconds