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

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

Original entry on oeis.org

2, 8, 34, 650, 12014, 1016492, 83761994, 32647369000, 12227920752840, 22181389298814376, 38166266554504010420, 323646210116765453608746, 2574827340090912815899810042, 102299512403818451392332665527950

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

I. Jensen, Table of n, a(n) for n = 1..18 [from the Jensen link below]
I. Jensen, Series Expansions for Self-Avoiding Walks
I. Jensen, Spanning Hamiltonian walks

Cf. A120443, A121785, A215527.

A333323 Number of self-avoiding closed paths on an n X n grid which pass through NW and SE corners.

Original entry on oeis.org

1, 3, 42, 1799, 232094, 92617031, 115156685746, 442641690778179, 5224287477491915786, 188825256606226776728029, 20879416139356164466643759334, 7057757437924198729598570424130207, 7287699030020917172151307665469211016474, 22973720258279267139936821063450448822110219653

Offset: 2

Seiichi Manyama, Mar 23 2020

nonn

			a(2) = 1;
   +--*
   |  |
   *--+
a(3) = 3;
   +--*--*   +--*--*   +--*
   |     |   |     |   |  |
   *--*  *   *     *   *  *--*
      |  |   |     |   |     |
      *--+   *--*--+   *--*--+

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 2..27
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 D2 (with offset 1).
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.

Cf. A007764, A333246, A333247, A333466.

Cf. A121785, A356610-A356616, A354511.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333323(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1).including(n * n)
    return cycles.len()
print([A333323(n) for n in range(2, 10)])

a(11) from Seiichi Manyama, Apr 07 2020

a(10) and a(12)-a(15) from Vaclav Kotesovec, Aug 16 2022 (computed by Anthony Guttmann)

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

Original entry on oeis.org

0, 12, 322, 14248, 1530196, 436619868, 343715004510, 766012555199052, 4914763477312679808, 91781780911712980966236, 5028368533802124263609489682, 813124448051069045700905179168520

Offset: 1

Eric W. Weisstein, Jun 04 2017

Paths of length zero are not counted here. - Andrew Howroyd, Jun 10 2017

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A288518.

Cf. A236753, A288033, A288148, A007764, A121785, A120443.

a(6)-a(12) from Andrew Howroyd, Jun 10 2017

A333509 Square array T(n,k), n >= 1, k >= 2, read by antidiagonals, where T(n,k) is the number of self-avoiding walks 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, 8, 1, 16, 29, 1, 32, 95, 80, 1, 64, 313, 426, 195, 1, 128, 1033, 2320, 1745, 444, 1, 256, 3411, 12706, 16347, 6838, 969, 1, 512, 11265, 69662, 154259, 112572, 25897, 2056, 1, 1024, 37205, 381964, 1454495, 1859660, 752245, 95292, 4279

Offset: 1

Seiichi Manyama, Mar 25 2020

			Square array T(n,k) begins:
    1,    1,      1,       1,        1, ...
    8,   16,     32,      64,      128, ...
   29,   95,    313,    1033,     3411, ...
   80,  426,   2320,   12706,    69662, ...
  195, 1745,  16347,  154259,  1454495, ...
  444, 6838, 112572, 1859660, 30549774, ...

Columns k=2-3 give: A333510, A333511.
Rows n=1-3 give: A000012, A000079(n+1), 2*A082574(n+1)+1.
T(n,n) gives A121785(n-1).

# 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)
    return paths.len()
def A333509(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([A333509(j + 1, i - j + 2) for i in range(9) for j in range(i + 1)])

A236753 Number of simple (non-intersecting) directed paths on the grid graph P_n X P_n.

Original entry on oeis.org

1, 28, 653, 28512, 3060417, 873239772, 687430009069, 1532025110398168, 9829526954625359697, 183563561823425961932572, 10056737067604248527218979485, 1626248896102138091401810358337184

Offset: 1

Jaimal Ichharam, Jan 30 2014

This is the number of directed paths on P_n X P_n of any length and also includes one zero length path per vertex. - Andrew Howroyd, May 27 2017

			For n=2 there are 4 zero length paths (one for each vertex), 8 paths with 1 one edge, 8 paths with 2 edges and 8 paths with 3 edges, so a(2)=28. - _Andrew Howroyd_, May 27 2017

Cf. A236690 (includes diagonal edges).

Cf. A288032, A007764, A121785, A120443.

a(n) = 2*A288032(n) + n^2. - Andrew Howroyd, Jun 10 2017

a(6) corrected and a(8) added from Jaimal Ichharam, Feb 13 2014

a(6)-a(8) corrected and a(9)-a(12) from Andrew Howroyd, May 27 2017

A121786 "Cow patches" on the square lattice (see Jensen web site for further information).

Original entry on oeis.org

1, 7, 160, 11408, 2522191, 1718769373, 3598611604598, 23098353998190640, 453839082673896579243, 27266319759961440667165921, 5005013940387988257218110301496, 2805250606288167736619664411164848668

Offset: 1

N. J. A. Sloane, Aug 30 2006

nonn

I. Jensen, Table of n, a(n) for n = 1..19 [from the Jensen link below]
M. Bousquet-Mélou, A. J. Guttmann, Iwan Jensen, Self-avoiding walks crossing a square, J. Phys. A: Math. Gen. 38 (2005) 9159-9181, Table 2.
I. Jensen, Series Expansions for Self-Avoiding Walks.
I. Jensen, Cow patches.

Cf. A007764, A121785.

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

A333323 Number of self-avoiding closed paths on an n X n grid which pass through NW and SE corners.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A333509 Square array T(n,k), n >= 1, k >= 2, read by antidiagonals, where T(n,k) is the number of self-avoiding walks 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

Crossrefs

Programs

Python

A236753 Number of simple (non-intersecting) directed paths on the grid graph P_n X P_n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A121786 "Cow patches" on the square lattice (see Jensen web site for further information).

Views

Author

Keywords

Links

Crossrefs

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