A091299 -id:A091299 - 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

A006069 Number of directed Hamiltonian cycles (or Gray codes) on n-cube with a marked starting node.

Original entry on oeis.org

2, 8, 96, 43008, 58018928640, 4587291356489073135452160

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 and the last node is 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,4,3,2; 2,3,4,1; 2,1,4,3; etc.

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

H. Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
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]
D. Sensarma, S. S. Sarma, GMDES: A graph based modified Data Encryption Standard algorithm with enhanced security, IJRET: International Journal of Research in Engineering and Technology 03:03 (2014), 653-660. See Section 2.2.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A003042, A006070, A091299, A091302, A159344.

a(n) = A003042(n)*2^n. - Max Alekseyev, Jun 15 2006

a(5) corrected by Jonathan Cross (jcross(AT)wcox.com), Oct 10 2001
Definition corrected by Max Alekseyev, Jun 15 2006
a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - 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

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

A284673 Number of (undirected) Hamiltonian paths in the n-hypercube graph Q_n.

Original entry on oeis.org

0, 1, 4, 72, 45696, 93749829120

Offset: 0

Eric W. Weisstein, Apr 01 2017

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

Cf. A091299.

Table[Total[Flatten[Table[Length[FindPath[HypercubeGraph[n], i, j, {2^n - 1}, All]], {j, 2^n}, {i, j - 1}]]], {n, 0, 4}] (* Eric W. Weisstein, Apr 01 2017 *)

a(n) = A091299(n) / 2 for n > 0. - Andrew Howroyd, May 09 2017

A342631 Number of Hamiltonian paths (or Gray codes) on n-cube with the origin as the starting node, up to a permutation of the coordinates.

Original entry on oeis.org

1, 1, 3, 238, 48828036

Offset: 1

Luc Rousseau, May 24 2021

			For n=2, the two Hamiltonian paths of the square that start at (0,0), i.e.,
  (0,0) -->-- (1,0)               (0,0)       (1,0)
                |                   |           |
                V        and        V           ^
                |                   |           |
  (0,1) --<-- (1,1)               (0,1) -->-- (1,1),
only account for one, as one is obtained from the other by the x <-> y permutation; so a(2) = 1.

Luc Rousseau, A C program that computes a(n)
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A003043, A091299.

C
```
/* See Rousseau link. */
```

a(n) = A003043(n) / n!.

A385185 Number of permutations of 0..n-1 which are binary Gray codes.

Original entry on oeis.org

1, 2, 2, 8, 4, 16, 24, 144, 36, 164, 192, 1168, 976, 5688, 10656, 91392, 11424, 67032, 61840, 403568, 258956, 1589080, 2520324, 22646880, 10898976, 67039504, 93326800, 819193248, 924489888, 7399407552, 16309883520, 187499658240, 11718728640

Offset: 1

Ross Drewe, Aug 03 2025

In a binary Gray code, the binary expansions of any two consecutive terms differ at a single bit position.

When n is odd, the binary weights of n and the first term in the permutation must have opposite parity, since otherwise it's not possible to step through all of 0,...,n-1.

			For n=5, the a(5) = 4 possible permutations which are Gray codes are
  1 3 2 0 4
  2 3 1 0 4
  4 0 1 3 2
  4 0 2 3 1
For n=8, a(8) = 144 includes 0 1 3 2 6 4 5 7 which is lexicographically smallest, and also includes the binary reflected Graycode 0 1 3 2 6 7 5 4.

Cf. A091299, A350784 (when beginning with 0).

function N = Gcode(L); H = hmap; N = 0; unused = uint8([0: L-1]); for i = 1:length(unused); g = unused(i); u = unused; u(i) = []; gray(g, u); end
function gray(g, u); curidx = g(end) + 1; d = H(curidx,:); if isscalar(u); if d(u+1); N = N + 1; end; else for j = 1: length(u); r = u(j); if d(r+1); nextg = [g r]; nextu = u; nextu(j) = []; gray(nextg, nextu); end; end; end; end
function map = hmap; map = false(L, L); S = uint8([0:L-1]); [X,Y] = meshgrid(S); X = X(:); Y = Y(:);
xb = de2bi(X); yb = de2bi(Y); for k = 1:L^2; v = sum(bitxor(xb(k,:), yb(k,:))); if v == 1; map(k) = true; end; end; end; end

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

a(2^n+1) = a(2^n)/2^(n-1) for n > 0. - Andrew Howroyd, Aug 04 2025

a(27)-a(33) from Andrew Howroyd, Aug 04 2025

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

A006069 Number of directed Hamiltonian cycles (or Gray codes) on n-cube with a marked starting node.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

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

Links

Crossrefs

Extensions

A284673 Number of (undirected) Hamiltonian paths in the n-hypercube graph Q_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A342631 Number of Hamiltonian paths (or Gray codes) on n-cube with the origin as the starting node, up to a permutation of the coordinates.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs