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,3

Comments

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

Links

Table of n, a(n) for n=1..16.

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

Example

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.

Crossrefs

Cf. A000532, A001184, A003763, A007764, A120443, A121785, A121789, A145157, A271507, A384173.

Sequence in context: A027486 A377742 A092664 * A260509 A385907 A073588

Adjacent sequences: A363574 A363575 A363576 * A363578 A363579 A363580

Keyword

nonn,hard,walk

Author

Lars Blomberg, Jun 10 2023

Extensions

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

Status

approved