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

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 3, 12, 3, 6, 49, 49, 6, 10, 146, 322, 146, 10, 15, 373, 1618, 1618, 373, 15, 21, 872, 7119, 14248, 7119, 872, 21, 28, 1929, 28917, 111030, 111030, 28917, 1929, 28, 36, 4118, 111360, 801756, 1530196, 801756, 111360, 4118, 36

Offset: 1

Andrew Howroyd, Jun 10 2017

Paths of length zero are not counted here.

			Table starts:
=================================================================
m\n|  1    2      3       4         5          6            7
---|-------------------------------------------------------------
1  |  0    1      3       6        10         15           21 ...
2  |  1   12     49     146       373        872         1929 ...
3  |  3   49    322    1618      7119      28917       111360 ...
4  |  6  146   1618   14248    111030     801756      5493524 ...
5  | 10  373   7119  111030   1530196   19506257    235936139 ...
6  | 15  872  28917  801756  19506257  436619868   9260866349 ...
7  | 21 1929 111360 5493524 235936139 9260866349 343715004510 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Rows 2-7 are A288516, A288527, A358800, A358801, A358802, A358803.
Main diagonal is A288032.
Cf. A231829, A064298, A271465, A271592, A120443, A001184, A145157, A003763.

A271507 Number of self-avoiding walks of any length from NW to SW corners on an n X n grid or lattice.

Original entry on oeis.org

1, 2, 11, 178, 8590, 1246850, 550254085, 741333619848, 3046540983075504, 38141694646516492843, 1453908228148524205711098, 168707605740228097581729005751, 59588304533380500951726150179910606, 64061403305026776755367065417308840021540

Offset: 1

Andrew Howroyd, Apr 08 2016

nonn

Main diagonal of A271465.

Cf. A007764, A000532, A001184, A145157, A120443, A003763.

A271465 = Cases[Import["https://oeis.org/A271465/b271465.txt", "Table"], {, }][[All, 2]];
a[n_] := A271465[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Sep 23 2019 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A271507(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A271507(n) for n in range(1, 10)])  # Seiichi Manyama, Mar 21 2020

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 8, 4, 1, 1, 5, 17, 17, 5, 1, 1, 6, 38, 52, 38, 6, 1, 1, 7, 78, 160, 160, 78, 7, 1, 1, 8, 164, 469, 824, 469, 164, 8, 1, 1, 9, 332, 1337, 3501, 3501, 1337, 332, 9, 1, 1, 10, 680, 3750, 16262, 22144, 16262, 3750, 680, 10, 1

Offset: 1

Andrew Howroyd, Dec 20 2024

These paths are also called Greek-key tours. The path can end anywhere.

			Array begins:
======================================================
m\n | 1 2   3    4     5      6        7         8 ...
----+-------------------------------------------------
  1 | 1 1   1    1     1      1        1         1 ...
  2 | 1 2   3    4     5      6        7         8 ...
  3 | 1 3   8   17    38     78      164       332 ...
  4 | 1 4  17   52   160    469     1337      3750 ...
  5 | 1 5  38  160   824   3501    16262     68591 ...
  6 | 1 6  78  469  3501  22144   144476    899432 ...
  7 | 1 7 164 1337 16262 144476  1510446  13506023 ...
  8 | 1 8 332 3750 68591 899432 13506023 180160012 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)

Main diagonal is A145157.
Rows 1..8 are A000012, A000027, A046994, A046995, A145156, A160240, A160241, A374307.
Cf. A332307, A064298, A271465, A271592, A288518.

T(m,n) = T(n,m).

A145156 Number of Greek-key tours on a 5 X n board; i.e., self-avoiding walks on 5 X n grid starting in top left corner.

Original entry on oeis.org

1, 5, 38, 160, 824, 3501, 16262, 68591, 304177, 1276805, 5522791, 23117164, 98562435, 411870513, 1740941765, 7267608829, 30557297042, 127482101761, 534250130959, 2227966210989, 9317736040747, 38847892461656, 162258421050635, 676389635980185, 2822813259030961, 11766012342819549

Offset: 1

Nathaniel Johnston, Oct 03 2008

nonn

From Andrew Howroyd, Nov 07 2015: (Start)
Greek Key Tours are self-avoiding walks that touch every vertex of the grid and start at the top-left corner.
The sequence may be enumerated using standard methods for counting Hamiltonian cycles on a modified graph with two additional nodes, one joined to a corner vertex and the other joined to all other vertices.
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..500
Nathaniel Johnston, Self-avoiding walks table of values
Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height, arXiv:2407.18205 [math.CO], 2024. See p. 30.
Index entries for linear recurrences with constant coefficients, signature (4,14,-54,-33,117,2,-84,-6,9,0,-14,0,-2).

Row 5 of A378938.

Cf. A046994, A046995, A145157.

G.f.: -x*(3*x^13 -3*x^12 +17*x^11 -11*x^10 +11*x^9 -21*x^8 +67*x^7 -29*x^6 -65*x^5 +45*x^4 +8*x^3 -4*x^2 -x -1) / ((x +1)*(x^6 -x^5 +8*x^4 -8*x^3 -2*x^2 +5*x -1)*(2*x^6 +11*x^2 -1)). [conjectured by Colin Barker, Nov 09 2015; proved by Jay Pantone, Klotz, and Sullivan, Aug 01 2024]

a(11)-a(15) added by Nathaniel Johnston, Oct 12 2008
a(16) added by Ruben Zilibowitz, Jul 10 2015
a(17) onwards from Andrew Howroyd, Nov 07 2015

A160240 Number of Greek-key tours on a 6 X n grid.

Original entry on oeis.org

1, 6, 78, 469, 3501, 22144, 144476, 899432, 5585508, 34092855, 206571444, 1241016042, 7407467656, 43975776229, 259779839242, 1528563721468, 8960651209082, 52368047294410, 305173796833144, 1774059940879290, 10289839706255591, 59564855651625602, 344177608427972004, 1985502681113986836

Offset: 1

Nathaniel Johnston, May 05 2009

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-left corner.

The sequence may be enumerated using standard methods for counting Hamiltonian cycles on a modified graph with two additional nodes, one joined to a corner vertex and the other joined to all other vertices. - Andrew Howroyd, Nov 07 2015

Andrew Howroyd, Table of n, a(n) for n = 1..500
Nathaniel Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height, arXiv:2407.18205 [math.CO], 2024. See p. 30.
Index entries for linear recurrences with constant coefficients, order 37.

Row 6 of A378938.

Cf. A046994, A046995, A145156, A145157.

See Links section for generating function. - Jay Pantone, Aug 01 2024

a(11) onwards from Andrew Howroyd, Nov 07 2015

A160241 Number of Greek-key tours on a 7 X n grid.

Original entry on oeis.org

1, 7, 164, 1337, 16262, 144476, 1510446, 13506023, 132712481, 1185979605, 11264671456, 100572103736, 935551716239, 8347069749600, 76604373779441, 683160282998544, 6213169249692192, 55392188422262591, 500676083630457127, 4462726297606450762, 40165465812088131228, 357958181000067374304

Offset: 1

Nathaniel Johnston, May 05 2009

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-left corner.

The sequence may be enumerated using standard methods for counting Hamiltonian cycles on a modified graph with two additional nodes, one joined to a corner vertex and the other joined to all other vertices. - Andrew Howroyd, Nov 07 2015

Andrew Howroyd, Table of n, a(n) for n = 1..500
Nathaniel Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height, arXiv:2407.18205 [math.CO], 2024. See p. 31.
Index entries for linear recurrences with constant coefficients, order 71.

Row 7 of A378938.

Cf. A046994, A046995, A145156, A145157.

See Links section for generating function. Jay Pantone, Aug 06 2024

a(11) onwards from Andrew Howroyd, Nov 07 2015

A331001 Number of symmetrical self-avoiding walks with maximum length on an n X n board which start in the upper left corner and go right on the first step.

Original entry on oeis.org

1, 1, 1, 2, 8, 24, 282, 888, 46933, 238119, 36027060, 187011538, 130162111969, 1084873972934, 2200211600730504, 18559765767843341, 174907641314142138422, 2355130982684196593401, 65250573687646264926302133, 884112393542714503429381555, 114482128183138374886637093070429, 2465467527044697154210112460659081

Offset: 1

S. Brunner, Feb 02 2020

If you allow going down on the first step you get two times a(n) for n > 1.

All symmetrical self-avoiding walks on a square board with odd length seem to have a 180-degree rotational symmetry, and all symmetrical self-avoiding walks on a square board with even length seem to have either vertically or horizontally reflection symmetry.

			The solutions for n=3 and n=4:
  n=3:  |    n=4:
  1     |    1          2
  >>v   |   >>>v   |   >v>
  v<<   |   v<<<   |   v<^<
  >>    |   >>>v   |   v>v^
        |    <<<   |   >^>^

S. Brunner, Python program.
Peter Kagey, Example of a(5) = 8.

Cf. A145157, A265914.

a(11)-a(20) from Andrew Howroyd, Feb 20 2020
a(21) from Andrew Howroyd, Oct 16 2024
a(22) from Oliver R. Bellwood, Jul 18 2025

A374307 Number of Greek-key tours on an 8 X n grid.

Original entry on oeis.org

1, 8, 332, 3750, 68591, 899432, 13506023, 180160012, 2510785227, 33330848454, 448079715759, 5893418278271, 77649390052196, 1011970457365017, 13165754032331389, 170232985496817728, 2195480228590892060, 28203099820000893198, 361391865363036263917, 4617813892310295762334

Offset: 1

Jay Pantone, Jul 23 2024

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-left corner.

Andrew Howroyd, Table of n, a(n) for n = 1..200
N. Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height., arXiv:2407.18205 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, order 203.

Row 8 of A378938.

Cf. A145157, A046994, A046995, A145156, A160240, A160241.

See Links section for generating function.

a(20) onwards from Andrew Howroyd, Dec 21 2024

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

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A271507 Number of self-avoiding walks of any length from NW to SW corners on an n X n grid or lattice.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A145156 Number of Greek-key tours on a 5 X n board; i.e., self-avoiding walks on 5 X n grid starting in top left corner.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A160240 Number of Greek-key tours on a 6 X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A160241 Number of Greek-key tours on a 7 X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A331001 Number of symmetrical self-avoiding walks with maximum length on an n X n board which start in the upper left corner and go right on the first step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A374307 Number of Greek-key tours on an 8 X n grid.