A096969 -id:A096969 - cp's OEIS frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

1, 4, 20, 276, 4324, 229348, 13535280, 3023313284, 745416341496, 730044829512632, 786671485270308848, 3452664855804347354220, 16652005717670534681315580, 331809088406733654427925292528, 7263611367960266490262600117251524

Offset: 1

David Bevan, Jul 19 2006

			From _Robert FERREOL_, Apr 03 2019: (Start)
a(3) = 20:
there are 4 paths similar to
  + - + - +
          |
  + - + - +
  |
  + - + - +
8 paths similar to
  + - + - +
  |       |
  +   + - +
  |   |
  +   + - +
and 8 paths similar to
  + - + - +
  |       |
  +   +   +
  |   |   |
  +   + - +
(End)

Jesper L. Jacobsen, Table of n, a(n) for n = 1..17
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Main diagonal of A332307.
Cf. A003685, A003695, A003778, A145402.
Cf. A003763, A000532, A001184, A145157, A271507, A007764, A121785, A121789.

a(n) = A096969(n) / 2 for n > 1.

More terms from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007

A096970 Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in the same row or column.

Original entry on oeis.org

1, 8, 1512, 22394880, 50657369241600, 28606505102329400524800, 5959275438217048853558620520448000

Offset: 1

John W. Layman, Jul 16 2004

Suggested by Leroy Quet, Jul 05 2004.

For n >= 2, number of (directed) Hamiltonian paths on the n X n rook graph. - Eric W. Weisstein, Dec 16 2013

			Among the 4 X 4 grids counted is:
1   2  3 10
15  6  5 11
14 13  4 12
16  7  8  9

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Rook Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A096969, A269561, A269565.

a(5) from Eric W. Weisstein, Dec 28 2013

a(6)-a(7) from Andrew Howroyd, Feb 29 2016

A158651 Number of directed Hamiltonian paths on the n X n king graph.

Original entry on oeis.org

1, 24, 784, 343184, 729237344, 13089822163800, 1659110130720710584, 1635069460917798701270872, 12308784500036123518164726610224, 721833220650131890343295654587745095696, 330596986686626406483380599328509951896788808144

Offset: 1

Eric W. Weisstein, Mar 23 2009

Number of open directed king's tours on the n X n board.

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A096969, A137891, A140521.

a(5) from Max Alekseyev, May 03 2009

a(6)-a(11) from Andrew Howroyd, Nov 15 2015

A193346 Number of (directed) Hamiltonian paths on the n X n X n grid graph.

Original entry on oeis.org

1, 144, 4960608, 55493434415544000

Offset: 1

Eric W. Weisstein, Jul 23 2011

A general purpose matrix-transfer method can be used to compute values up to a(4). Using a diagonal sweep from one corner to the opposite corner will help to reduce the number of states. - Andrew Howroyd, Dec 20 2015

Schram & Schiessel (see Links) quote a different result for a(4): 27747833510015886 undirected Hamiltonian walks, which would double to 55495667020031772 directed Hamiltonian walks. However, that number is not divisible by 8 and thus cannot be correct. - Arun Giridhar, Dec 15 2015

			For n = 1, there is a trivial Hamiltonian path of length 0.
For n = 2, the 144 paths fall in three different equivalence classes. Two of the three classes can be derived by taking a Hamiltonian cycle on a cube and deleting a single edge. The third class is a spiral path that ends at the opposite corner from its starting point.

Raoul D. Schram and Helmut Schiessel, Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 46 (2013), 485001.
Raoul D. Schram and Helmut Schiessel, Corrigendum: Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding, Journal of Physics A: Mathematical and Theoretical, vol 49 (2016), 369501.
Jamie Shepard, Solvability and Difficulty of the Snake Puzzle in the Cube and its Topological Variants, Honors Thesis, Andrews Univ. (2024) Art. No. 290.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A096969.

a(4) from Andrew Howroyd, Nov 15 2015

a(1) corrected by Arun Giridhar, Dec 20 2015

cp's OEIS Frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A096970 Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in the same row or column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A158651 Number of directed Hamiltonian paths on the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A193346 Number of (directed) Hamiltonian paths on the n X n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions