| Displaying 1-9 of 9 results found.
page
1
Number of directed Hamiltonian cycles (or Gray codes) on n-cube.
(Formerly M2053)
+10
12
1, 2, 12, 2688, 1813091520, 71676427445141767741440
COMMENTS
Finding a(6) is Problem 43 in the Knuth reference.
REFERENCES
Martin Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
EXTENSIONS
a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012
Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.
+10
10
1, 1, 6, 1344, 906545760, 35838213722570883870720
COMMENTS
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 and the last node is adjacent to the first; and then dividing the total by 2^(n+1) because the starting node and the direction do not really matter.
The number is a multiple of n!/2 since any directed cycle starting from 0^n induces a permutation on the n bits, namely the order in which they first get set to 1.
EXAMPLE
The 2-cube has a single cycle consisting of all 4 edges.
MATHEMATICA
Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* Eric W. Weisstein, Apr 01 2017 *)
EXTENSIONS
a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012
Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.
+10
9
2, 8, 144, 91392, 187499658240
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.
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
(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
Number of equivalence classes of directed Hamiltonian cycles (or Gray codes) in the binary n-cube with one node marked.
+10
8
1, 1, 2, 112, 15109096, 99550593673808010752
REFERENCES
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.
EXTENSIONS
a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012, who also provided a more precise definition. - N. J. A. Sloane, Sep 06 2012
Number of Hamiltonian paths (or Gray codes) on n-cube with a marked starting node.
(Formerly M2112)
+10
7
1, 2, 18, 5712, 5859364320
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. Finally, divide by 2^n since the starting node really doesn't matter.
Also, the number of strings s of length 2^n - 1 over the alphabet {1,2,...,n} with the property that every contiguous subblock has some letter that appears an odd number of times.
REFERENCES
M. Gardner, Mathematical Games, Sci. Amer. Vol. 228 (No. 4, Apr. 1973), p. 111.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Number of Hamiltonian paths on n-cube which are strictly not cycles.
(Formerly M5295)
+10
7
0, 0, 48, 48384, 129480729600
COMMENTS
Number of Gray codes of length n which strictly do not close.
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 and the last node is not adjacent to the first.
REFERENCES
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
EXAMPLE
There are no such paths for n=1 or n=2 (the square). For n = 3 every path has to end at the node of the cube that is diametrically opposite to the start. There are 16 choices for the start and for each start there are 3 Hamiltonian paths that end at the opposite node, so a(3) = 3*16 = 48.
EXTENSIONS
a(5) from Greg Barton (greg_barton(AT)yahoo.com), May 24 2004
Number of Hamiltonian cycles in the n-hypercube up to automorphism.
+10
4
1, 1, 1, 9, 237675, 777739016577752714
COMMENTS
Here we count equivalence classes under the full automorphism group of the n-cube. - N. J. A. Sloane, Sep 06 2012 a(4) is due to Gilbert and a(5) is due to Dejter & Delgado.
a(n) is, in Abbott's terminology, h*(n); see (2) and (3) which yield a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n) [Note that we have written sqrt(294) for 7 sqrt(6)].
Unfortunately, the lower bound seems incompatible with the known values of a(n), even for a(3) and a(4) which were known to Abbott.
Looking at Abbot's paper, at least one error is the claim "it is easy to verify that (12) implies (3)."
(12) is h(m+3) >= 6^2^m h(m), which implies h(m) >= 6^2^(m-3) for m >= 4, or h(m) >= 2/5 * (6^2^(m-3)) for m >= 1, but certainly doesn't imply (3) h(m) >= (7 sqrt(6))^(2^n-4). (End)
FORMULA
a(n) < n^(2^n).
a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n) and a(n) >= A066037(n)/ A000165(n) due to Abbott 1966. [Warning: see Comments above!]
EXAMPLE
There are six Hamiltonian cycles in the cube, but they are isomorphic so a(3) = 1.
Number of paths (without loops) in graph of n-dimensional hypercube starting at point (0,0,0,...,0) and ending at (1,1,1,...,1).
+10
3
1, 2, 18, 6432, 18651552840
COMMENTS
Terms up to a(5)=18651552840 confirmed by independent computation. [ Joerg Arndt, Aug 07 2012]
EXAMPLE
a(2) = 2 because there are 2 paths: 00,01,11 and 00,10,11
AUTHOR
Avi Peretz (njk(AT)netvision.net.il), Feb 22 2001
EXTENSIONS
Added a(5), based on http://teamikaria.com/4dforum/viewtopic.php?f=5&t=1211 Dmitry Kamenetsky, Aug 28 2009
Number of order-preserving Hamiltonian paths in the n-cube (Gray codes); see the comments for the precise definition of order-preserving.
+10
0
1, 1, 1, 1, 1, 10, 123, 1492723
COMMENTS
An order-preserving Hamiltonian path in the n-cube is a listing S_1,...,S_N of all N:=2^n many subsets of [n]:={1,2,...,n}, such that if S_j is a subset of S_i then j <= i+1. For the counting we ignore paths that differ only by renaming elements of the ground set (=automorphisms of the n-cube), i.e., without loss of generality every such path starts as follows: S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4},..., S_{2n-2}={n-1}, S_{2n-1}={n-1,n}, S_{2n}={n} (after visiting the set {n}, there are multiple ways to proceed).
It is shown in [Felsner, Trotter 95] that an order-preserving Hamiltonian path is level-accurate in the following sense: After visiting a set of size k, the path will never visit a set of size (k-2) (*).
For odd n we will have S_N={1,2,...,n} (i.e., |S_N|=n) and for even n we will have |S_N|=n-1.
Hamiltonian paths that have property (*) have been constructed in [Savage, Winkler 95] for all n (but these paths are not order-preserving).
For n=8,9,10 we know that a(n)>=1. It is unknown whether a(n)>=1 for n>=11 (i.e., it is not known whether such order-preserving paths exist). Some partial results have been obtained in [Biro, Howard 09].
EXAMPLE
For n=4 the a(4)=1 solution is S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4}, S_9={2,4}, S_10={1,2,4}, S_11={1,4}, S_12={1,3,4}, S_13={1,3}, S_14={1,2,3}, S_15={1,2,3,4}, S_16={2,3,4}.
Search completed in 0.011 seconds
|