A120443 -id:A120443 - cp's OEIS frontend

A096969 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 adjacent cells (horizontally or vertically).

1, 8, 40, 552, 8648, 458696, 27070560, 6046626568, 1490832682992, 1460089659025264, 1573342970540617696, 6905329711608694708440, 33304011435341069362631160, 663618176813467308855850585056, 14527222735920532980525200234503048

Offset: 1

John W. Layman, Jul 16 2004, at the suggestion of Leroy Quet, Jul 05 2004

Number of directed Hamiltonian paths in (n X n)-grid graph. - Max Alekseyev, May 03 2009

			One of the 8648 numberings of a 5 X 5 grid is
.
  3---2---1  20--21
  |           |   |
  4  17--18--19  22
  |   |           |
  5  16--15--14  23
  |           |   |
  6   9--10  13  24
  |   |   |   |   |
  7---8  11--12  25

Andrew Howroyd, Table of n, a(n) for n = 1..17
Nicolas Bělohoubek, All possible paths in 4th term (552) presented by A..D 1..4 coordination system.
Nicolas Bělohoubek, All possible paths in 5th term (8648) presented by A..E 1..5 coordination system.
Nicolas Bělohoubek, All possible paths in 5th term (8648) in image, blue to red.
Stéphane Duguay and Steven Pigeon, Comparison of Pixel Correlation Induced by Space-Filling Curves on 2D Image Data, The 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (Metz, France, 2019) Vol. 1, 294-297.
Mary Grace Hanson and David A. Nash, Minimal and maximal Numbrix puzzles, arXiv:1706.09389 [math.CO], 2017.
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. A120443, A096970, A143246, A137891, A158651.

Conjecture: Limit_{n->oo} log_(n+1)!(a(n+1)) - log_n!(a(n)) = c, where 0.09 < c < 0.11. - Nicolas Bělohoubek, Jun 12 2022

a(7) from Giovanni Resta, May 12 2006

a(8)-a(15) added by Andrew Howroyd, Dec 20 2015

A268894 Number of Hamiltonian paths in C_n X P_n.

Original entry on oeis.org

1, 4, 144, 4016, 152230, 14557092, 1966154260, 761411682704, 411068703517542, 684434716944151900, 1572754514153890134760, 11579615738168536799184984, 117186519917858266359631481672, 3877921919790491112398750141807648, 176258463464553583688099296874564393850, 26493868301658838913487471166447301509560736

Offset: 1

Andrew Howroyd, Feb 15 2016

nonn

This is the number of undirected paths.

Artem M. Karavaev, Hamilton Paths
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Cf. A003763, A222197, A120443, A268838.

Cf. A003752, A003732.

A265914 Number of Hamiltonian paths on an n X n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Original entry on oeis.org

1, 1, 3, 38, 549, 28728, 1692417, 377919174, 93177169027, 91255604983167, 98333935794279062, 431583106977641773651, 2081500714709464758363648, 41476136050841717002906372881, 907951420995033325255530074961505, 82829339673122474155192677008453291270

Offset: 1

Luca Petrone, Dec 18 2015

For odd n > 1 the only symmetry possible is rotation by 180 degrees. For even n the only symmetries are reflections either horizontally or vertically. - Andrew Howroyd, Apr 15 2016

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. 5.
Jean-Marc Mayer, Claude Guez, and Jean Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.

Cf. A120443, A209077, A068393.

a(9)-a(15) from Andrew Howroyd, Apr 15 2016

a(16) from Oliver R. Bellwood, Jun 06 2025

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

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

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

A366399 Triangle read by rows: T(n,k) is the number of paths traveling orthogonally on an n X k grid that visit every cell.

Original entry on oeis.org

1, 1, 4, 1, 8, 20, 1, 14, 62, 276, 1, 22, 132, 1006, 4324, 1, 32, 336, 3610, 26996, 229348, 1, 44, 688, 12010, 109722, 1620034, 13535280, 1, 58, 1578, 38984, 602804, 12071462, 175905310, 3023313284, 1, 74, 3190, 122188, 2434670, 82550864, 1449655468, 43551685370, 745416341496

Offset: 1

Douglas Boffey, Oct 09 2023

			T(n,k) is a triangular array read by rows:
  1,
  1,  4,
  1,  8, 20,
  1, 14, 62, 276,
  ...
T(2,2) = 4:
  +---+---+  +---+---+  +---+---+  +---+---+
  |   |   |  |   |   |  |   |   |  |   |   |
  | **|** |  | * | * |  | **|** |  | **|** |
  |   | * |  | * | * |  | * |   |  | * | * |
  +---+---+  +---+---+  +---+---+  +---+---+
  |   | * |  | * | * |  | * |   |  | * | * |
  | **|** |  | **|** |  | **|** |  | * | * |
  |   |   |  |   |   |  |   |   |  |   |   |
  +---+---+  +---+---+  +---+---+  +---+---+

See A332307 for another version.

Cf. A120443 (T(n,n)), A366411 (row sums).

More terms (using A332307) from Pontus von Brömssen, Oct 09 2023

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

A096969 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 adjacent cells (horizontally or vertically).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A268894 Number of Hamiltonian paths in C_n X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A265914 Number of Hamiltonian paths on an n X n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

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

A366399 Triangle read by rows: T(n,k) is the number of paths traveling orthogonally on an n X k grid that visit every cell.

Views

Author

Keywords

Examples

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