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

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

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.

Sequence in context: A118184 A027486 A092664 * A260509 A073588 A068338

Adjacent sequences: A363574 A363575 A363576 * A363578 A363579 A363580

Keyword

nonn,hard,walk,more

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

Status

approved