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

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Original entry on oeis.org

1, 1, 2, 8, 86, 1770, 88418, 8934966, 2087813834, 1013346943033, 1111598871478668, 2568944901392936854, 13251059359839620127088, 145194816279817259193401518, 3524171261632305641165676374930, 182653259988707123426135593460533473

Offset: 1

Russ Cox, Mar 15 1996

Number of walks reaching each cell exactly once.

Oliver R. Bellwood, Table of n, a(n) for n = 1..20 (first 19 terms from KeyTo9(AT)Fans, Ed Wynn)
KeyTo9(AT)Fans, Counting paths in a grid - Chinese web page giving the sequence up to 18 items.
Douglas M. McKenna, Tendril Motifs for Space-Filling, Half-Domino Curves, in: Bridges Finland Conference Proceedings, 2016, pp. 119-126.
Douglas M. McKenna, Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing Medium?, Bridges Conf. Proc.; Math., Art, Music, Architecture, Culture (2023) 91-98.

Main diagonal of A271592.
Cf. A181688, A181689, A014524, A014585.
Cf. A001184, A145157, A120443, A003763, A271507, A007764, A121785, A121789.
See also A350148.

More terms from Zhao Hui Du, Jul 08 2008
Edited by Franklin T. Adams-Watters, Jul 03 2009
Name clarified by Andrew Howroyd, Apr 10 2016

A121785 "Spanning walks" on the square lattice (see Jensen web site for further information).

Original entry on oeis.org

8, 95, 2320, 154259, 30549774, 17777600753, 30283708455564, 152480475641255213, 2287842813828061810244, 102744826737618542833764649, 13848270995235582268846758977770

Offset: 1

N. J. A. Sloane, Aug 30 2006

nonn

Number of Hamiltonian paths in the graph P_{n+1} X P_{n+1} starting at any of the n+1 vertices on one side of the graph and terminating at any of the n+1 vertices on the opposite side. - Andrew Howroyd, Apr 10 2016

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 1..26
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, table D1.
I. Jensen, Series Expansions for Self-Avoiding Walks
I. Jensen, Spanning walks (terms)

Cf. A000532, A001184, A121789, A215527.

Cf. A333323, A356610-A356616, A354511.

A068381 Number of partitions of n X n checkerboard by two edgewise-connected sets which produce the maximum n^2-2n+2 frontier edges between the two sets.

Original entry on oeis.org

12, 32, 96, 648, 7736, 228424, 11974112, 1599762776, 382467306272, 234367651907856, 258981528765867728, 733498025032488425464, 3770347483688546402804760, 49588653272896250824990166768

Offset: 2

R. H. Hardin, Mar 04 2002

nonn

Not divided by 4 because that property may not continue.

Each partition is counted twice in this sequence. The sequence can be computed by counting Hamiltonian paths on a n-1 x n-1 grid that start at any vertex on the grid boundary and terminate at another boundary vertex. Counts for whether the path starts or terminates on a corner or non-corner need to be computed separately as there are different multiplication factors. - Andrew Howroyd, Apr 13 2016

			Illustration of a(2)=6*2:
    __.__     __.__     __.__    __.__     __.__     __.__
   |__|  |   |  |__|   |   __|  |__   |   |__.__|   |  |  |
   |__.__|   |__.__|   |__|__|  |__|__|   |__.__|   |__|__|
Illustration of relation of a Hamiltonian path in a 3 x 3 grid to solutions of a(4):
                 .__.__.__.__.   .__.__.__.__.   .__.__.__.__.   .__.__.__.__.
   .__.__        |__.__.__.  |   |  |__.__.  |   |__.__.__.  |   |  |__.__.  |
    __.__|  <=>  |  .__.__|  |   |  .__.__|  |   |  .__.__|  |   |  .__.__|  |
   |__.__.       |  |__.__.__|   |  |__.__.__|   |  |__.__.  |   |  |__.__.  |
                 |__.__.__.__|   |__.__.__.__|   |__.__.__|__|   |__.__.__|__|

Cf. A068392, A068393.

Cf. A001184, A000532, A121789.

a(7)-a(15) from Andrew Howroyd, Apr 13 2016

A333571 Square array T(n,k), n >= 1, k >= 2, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in the n X k grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 8, 6, 1, 2, 16, 14, 10, 1, 2, 32, 34, 38, 14, 1, 2, 64, 80, 162, 74, 20, 1, 2, 128, 190, 650, 426, 170, 26, 1, 2, 256, 450, 2728, 2166, 1594, 338, 34, 1, 2, 512, 1066, 11250, 12014, 12908, 4374, 724, 42, 1, 2, 1024, 2526, 46984, 62714, 119364, 47738, 14640, 1448, 52

Offset: 1

Seiichi Manyama, Mar 27 2020

			Square array T(n,k) begins:
   1,  1,   1,    1,     1,     1,      1, ...
   2,  2,   2,    2,     2,     2,      2, ...
   4,  8,  16,   32,    64,   128,    256, ...
   6, 14,  34,   80,   190,   450,   1066, ...
  10, 38, 162,  650,  2728, 11250,  46984, ...
  14, 74, 426, 2166, 12014, 62714, 340510, ...

Seiichi Manyama, Antidiagonals n = 1..14, flattened

Columns k=2-3 give: A333574, A333575.
Rows n=1-3 give: A000012, 2*A000012, A000079.
T(n,n) gives A121789(n-1).
Cf. A333509.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(start, goal, n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333571(n, k):
    if n == 1: return 1
    s = 0
    for i in range(1, n + 1):
        for j in range(k * n - n + 1, k * n + 1):
            s += A(i, j, k, n)
    return s
print([A333571(j + 1, i - j + 2) for i in range(11) for j in range(i + 1)])

A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded.

Original entry on oeis.org

1, 1, 4, 51, 660, 30745, 1621471, 312637285, 72599875346, 60968508324409, 64128000370443037, 240651566540823214362, 1162174738476331286327484, 19776621796151182708398884540, 441809773825445785471324877668710

Offset: 1

David Lawrence, Oct 31 2019

Given an n X n grid, start from any outside edge, enter the grid, and visit every square. 1 X 1 is a trivial example. 2 X 2 can only be traversed clockwise or counterclockwise (therefore considered the same solution). For 3 X 3 with the cells labeled ABC/DEF/GHI, the four solutions are ADEBCFIHG, ADGHIFEBC, ADGHIFCE and ADGHEBCFI. All others are rotations or reflections.

Discovered programmatically by exhaustive recursive search.

			All distinct paths through a 1 X 1 labyrinth visiting all cells.
  +  +
  |**|
  +--+
.
All distinct paths through a 2 X 2 labyrinth visiting all cells.
  +  +--+
  |  |**|
  +  +  +
  |     |
  +--+--+
.
All distinct paths through a 3 X 3 labyrinth visiting all cells.
  +  +--+--+
  |  |     |
  +  +  +  +
  |     |  |
  +--+--+  +
  |**      |
  +--+--+--+
.
  +  +--+--+
  |  |   **|
  +  +  +--+
  |  |     |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |**|  |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |  |  |
  +  +  +  +
  |     |**|
  +--+--+--+

David Lawrence, All paths up to 4 X 4

Cf. A120443, A121789, A145157, A265914.

a(8)-a(15) from Andrew Howroyd, Oct 31 2019

A363577 Number of inequivalent Hamiltonian paths starting in the lower left corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent).

Original entry on oeis.org

1, 1, 3, 23, 347, 10199, 683227, 85612967, 25777385143, 14396323278040, 19799561204761862, 50351228336401026361, 319210377672595552740369, 3736517399241599771428011100, 109790442395888863208285555153329, 5952238893391106787883489313797219949

Offset: 1

Lars Blomberg, Jun 10 2023

Equivalently, number of inequivalent Hamiltonian paths starting in a corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent). - Martin Ehrenstein, Jul 08 2023

			There are 3 paths for n=3:
  +--+--+    +--+--+    +--+  +
  |     |    |     |    |  |  |
  +  +  +    +  +--+    +  +  +
  |  |  |    |  |       |  |  |
  +  +--+    +  +--+    +  +--+
A fourth path:
  +--+--+
        |
  +--+  +
  |  |  |
  +  +--+
is the same as the second one in the row above after a 90-degree rotation.
All paths starting E are the same as the corresponding ones starting N after reflection in the forward diagonal.

Oliver R. Bellwood, Heitor P. Casagrande, and William J. Munro, Fractal Path Strategies for Efficient 2D DMRG Simulations, arXiv:2507.11820 [cond-mat.str-el], 2025. See p. 4.
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. A000532, A001184, A003763, A007764, A120443, A121785, A121789, A145157, A271507, A384173.

a(1) added by N. J. A. Sloane, Jun 10 2023
a(8)-a(9) from Martin Ehrenstein, Jul 08 2023
a(10)-a(16) from Oliver R. Bellwood, Jun 06 2025

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

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A121785 "Spanning walks" on the square lattice (see Jensen web site for further information).

Views

Author

Keywords

Comments

Links

Crossrefs

A068381 Number of partitions of n X n checkerboard by two edgewise-connected sets which produce the maximum n^2-2n+2 frontier edges between the two sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A333571 Square array T(n,k), n >= 1, k >= 2, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in the n X k grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A363577 Number of inequivalent Hamiltonian paths starting in the lower left corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions