A006069 -id:A006069 - cp's OEIS frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Original entry on oeis.org

1, 2, 12, 2688, 1813091520, 71676427445141767741440

Offset: 1

N. J. A. Sloane

Finding a(6) is Problem 43 in the Knuth reference.

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

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391 [cs.DM], 2010. [There may be errors - see Haanpaa and Ostergard, 2012]
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
John Jungck, Genetic Codes as Codes: Towards a Theoretical Basis for Bioinformatics, International Symposium on Mathematical and Computational Biology (BIOMAT 2008), see p. 19.
Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the n-bit Gray codes by restricted random generation of permutations of 1 to 2^n, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069 divided by 2^n.

Cf. A006070, A091299, A003043, A091302, A066037, A159344, A180026.

a(n) = 2 * A066037(n).

a(6) from Michel Deza, Mar 28 2010

a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012

A066037 Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.

Original entry on oeis.org

1, 1, 6, 1344, 906545760, 35838213722570883870720

Offset: 1

John Tromp, Dec 12 2001

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.

			The 2-cube has a single cycle consisting of all 4 edges.

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391 [cs.DM], 2010. [There may be errors - see Haanpaa and Ostergard, 2012]
R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
Harary, Hayes, and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 277-289.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069/2^(n+1) and A003042/2.
Cf. A006070, A091299, A003043, A091302.
Cf. A236602 (superset). - Stanislav Sykora, Feb 01 2014

Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* Eric W. Weisstein, Apr 01 2017 *)

a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012
Name clarified by Eric W. Weisstein, May 06 2019

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

Original entry on oeis.org

2, 8, 144, 91392, 187499658240

Offset: 1

N. J. A. Sloane, Feb 20 2004

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.

			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.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph

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

Cf. A003042, A066037, A091302, A284673.

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

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

A091302 Number of equivalence classes of directed Hamiltonian cycles (or Gray codes) in the binary n-cube with one node marked.

Original entry on oeis.org

1, 1, 2, 112, 15109096, 99550593673808010752

Offset: 1

N. J. A. Sloane, following a suggestion of Gordon Royle, Feb 20 2004

nonn

Equals A066037(n)/(n!/2). See A006069, A003042, A066037 for more information.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391v1 [There may be errors - see Haanpaa and Ostergard, 2012]
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp., 88 (2014) 979-995. Final version available from http://users.tkk.fi/pat/.

Cf. A006069, A003042, A066037, A159344.

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

A003043 Number of Hamiltonian paths (or Gray codes) on n-cube with a marked starting node.

Original entry on oeis.org

1, 2, 18, 5712, 5859364320

Offset: 1

N. J. A. Sloane

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.

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

Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).

Cf. A091299, A006069, A006070, A003042, A066037, A091302, A179926.

a(n) = A091299(n)/2^n.

a(5) (from A091299) from Max Alekseyev, Jul 09 2006

Alternative description added by Jeffrey Shallit, Feb 02 2013

A006070 Number of Hamiltonian paths on n-cube which are strictly not cycles.

Original entry on oeis.org

0, 0, 48, 48384, 129480729600

Offset: 1

N. J. A. Sloane

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.

			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.

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

Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A006069, A091299.

a(n) = A091299(n) - A006069(n). - Andrew Howroyd, Dec 25 2021

a(5) from Greg Barton (greg_barton(AT)yahoo.com), May 24 2004

A159344 Number of Hamiltonian cycles in the n-hypercube up to automorphism.

Original entry on oeis.org

1, 1, 1, 9, 237675, 777739016577752714

Offset: 1

Charles R Greathouse IV, Jan 25 2012

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.
Comments on Abbott's (1966) lower bound, from Charles R Greathouse IV and David Applegate (Sequence Fans Mailing List, Dec 06 2012: (Start)
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)

			There are six Hamiltonian cycles in the cube, but they are isomorphic so a(3) = 1.

H. L. Abbott, Hamiltonian circuits and paths on the n-cube, Canad. Math. Bull., 9 (1966), pp. 557-562.
Yury Chebiryak and Daniel Kroening, Towards a classification of Hamiltonian cycles in the 6-cube, Journal on Satisfiability, Boolean Modeling and Computation 4 (2008) pp. 57-74.
I. J. Dejter and A. A. Delgado, Classes of Hamiltonian cycles in the 5-cube, J. Combinat. Math, Combinat. Comput, 61 (2007), pp. 81-95.
R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.
E. N. Gilbert, Gray codes and paths on the n-cube, Bell Syst. Tech. J. 37 (1958), pp. 815-826.
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp., 83 (2014), 979-995.
Frank Ruskey, Combinatorial Generation (2003), see ch. 6.7.
D. H. Smith, Hamiltonian circuits on the n-cube, Canadian Mathematical Bulletin 17 (1975), pp. 759-761.

Cf. A003042, A006069, A066037, A091302.

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

a(6) from Haanpaa & Ostergard 2012. - N. J. A. Sloane, Sep 06 2012

Edited by N. J. A. Sloane, Dec 16 2012

A059783 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).

Original entry on oeis.org

1, 2, 18, 6432, 18651552840

Offset: 1

Avi Peretz (njk(AT)netvision.net.il), Feb 22 2001

Terms up to a(5)=18651552840 confirmed by independent computation. [Joerg Arndt, Aug 07 2012]

			a(2) = 2 because there are 2 paths: 00,01,11 and 00,10,11

J. Berestycki, É. Brunet, and Z. Shi, Accessibility percolation with backsteps, arXiv preprint arXiv:1401.6894 [math.PR], 2014.
Higher Dimensions Number of simple paths in a tesseract [From _Dmitry Kamenetsky_, Aug 28 2009]

Cf. A007764.

Cf. A091299, A006069, A006070, A003042, A066037, A091302.

Added a(5), based on http://teamikaria.com/4dforum/viewtopic.php?f=5&t=1211 Dmitry Kamenetsky, Aug 28 2009

Corrected offset Alex Ratushnyak, Aug 07 2012

A259839 Number of order-preserving Hamiltonian paths in the n-cube (Gray codes); see the comments for the precise definition of order-preserving.

Original entry on oeis.org

1, 1, 1, 1, 1, 10, 123, 1492723

Offset: 0

Torsten Muetze, Jul 06 2015

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

			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}.

C. Biro and D. Howard, The first three levels of an order preserving Hamiltonian path in the subset lattice, Order, 26(2):101-107, 2009.
S. Felsner and W. Trotter, Colorings of diagrams of interval orders and alpha-sequences of sets, Discrete Math., 144(1-3):23-31, 1995.
C. Savage and P. Winkler, Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A, 70(2):230-248, 1995.

Cf. A003042, A003043, A006069, A006070, A066037, A091302, A159344.

cp's OEIS Frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A066037 Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A091302 Number of equivalence classes of directed Hamiltonian cycles (or Gray codes) in the binary n-cube with one node marked.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A003043 Number of Hamiltonian paths (or Gray codes) on n-cube with a marked starting node.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A006070 Number of Hamiltonian paths on n-cube which are strictly not cycles.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A159344 Number of Hamiltonian cycles in the n-hypercube up to automorphism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A059783 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).

Views

Author

Keywords

Comments

Examples