A003763 -id:A003763 - cp's OEIS frontend

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).

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

A380451 Number of disjoint-path coverings for 2 X n rectangular grids, admitting zero-length paths.

Original entry on oeis.org

2, 15, 95, 604, 3835, 24349, 154594, 981531, 6231827, 39566420, 251210695, 1594958889, 10126534850, 64294264119, 408209961239, 2591761096236, 16455320099427, 104476280613925, 663329132764770, 4211535247894499, 26739409243687915, 169770870862086564, 1077890252944724559, 6843620413168932241, 43450750418785228802

Offset: 1

Anton M. Alekseev, Jun 22 2025

Can be computed using transfer matrix method. Suppose we build the coverage column-by-column, extending the "border" with each step by adding edges and vertices.
Upon enumerating all configurations of the border (8 configurations + a case of two paths connected earlier) and adding the start/end states, one can analyze which configuration can be obtained at the next step and build an 11 X 11 transfer matrix:
  "two isolated nodes"  1 1 1 1 1 0 1 1 1 0 1
  "top tail"            1 1 1 1 1 0 1 1 1 0 1
  "bottom tail"         1 1 1 1 1 0 1 1 1 0 1
  "vertical edge"       1 1 1 1 0 1 1 1 0 0 1
  "two indep. tails"    1 1 1 1 1 0 1 1 1 0 1
  "two connected tails" 1 1 1 1 0 1 1 1 0 0 1
  "upper hook"          1 0 1 1 0 0 0 1 0 0 1
  "lower hook"          1 1 0 1 0 0 1 0 0 0 1
  "all three edges"     1 0 0 1 0 0 0 0 0 0 1
  start                 1 0 0 1 0 0 0 0 0 0 1
  end                   0 0 0 0 0 0 0 0 0 0 0
The sequence of interest can be obtained by multiplying the matrix to the power of N by a vector -- all zeros except the "start" position value equal to 1.
Also, characteristic polynomial of the transfer matrix is x^6 * (x+1) * (x^4-7x^3+4x^2+x-1), hence the recurrence relation is also easily obtainable through the Cayley-Hamilton theorem: x^(n) = 7*x^(n-1) - 4*x^(n-2) - x^(n-3) + x^(n-4) => a(n) = 7 * a(n-1) - 4 * a(n-2) - a(n-1) + a(n-4). Roots 0 and -1 do not contribute to the formula.
Configurations listed in the order as in the transfer matrix (the border on the pictures is to the right):
  *    -*      *    *    -*
     ,     ,      , |  ,    ,
  *     *     -*    *    -*
       *    -*
   ... | ...   (the case where tails have been connected earlier),
       *    -*
  *-*      *    *-*
    |  ,   |  ,   |
    *    *-*    *-*

			For n = 1 the a(1) = 2 solutions are
  * *    *-*
For n = 2 the a(2) = 15 solutions are
  * *
  * *
  *-*    * *    * *    * *
                |        |
  * *    *-*    * *    * *
  *-*    *-*    * *    * *    *-*    * *
  |        |      |    |             | |
  * *    * *    *-*    *-*    *-*    * *
  *-*    *-*    * *    *-*
  | |      |    | |    |
  * *    *-*    *-*    *-*

R. P. Stanley, Enumerative Combinatorics, Cambridge University Press (2012).

Index entries for linear recurrences with constant coefficients, signature (7,-4,-1,1).

Cf. A003763.

a:=n->`if`(n<5,[2,15,95,604][n],7*a(n-1)-4*a(n-2)-a(n-3)+a(n-4));

a[n_]:=LinearRecurrence[{7,-4,-1,1},{2,15,95,604},n][[-1]]

from functools import reduce;
a=lambda n:reduce(lambda s,_:s+[7*s[-1]-4*s[-2]-s[-3]+s[-4]],range(4,n),[2,15,95,604])[n-1]

Recurrence: a(n) = 7*a(n-1) - 4*a(n-2) - a(n-3) + a(n-4), where a(1) = 2, a(2) = 15, a(3) = 95, a(4) = 604 (for proof, see the comments section).

a(16) onwards corrected by Anton M. Alekseev, Jul 06 2025

cp's OEIS Frontend

A238818 Number of Hamiltonian cycles on 2n X 2n grid with at least the symmetries of two reflections and 180-degree rotation.

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

A380451 Number of disjoint-path coverings for 2 X n rectangular grids, admitting zero-length paths.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions