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

%I #16 Feb 16 2025 08:34:05

%S 1,1,3,23,347,10199,683227,85612967,25777385143

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

%C 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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>

%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>

%e There are 3 paths for n=3:

%e +--+--+ +--+--+ +--+ +

%e | | | | | | |

%e + + + + +--+ + + +

%e | | | | | | | |

%e + +--+ + +--+ + +--+

%e A fourth path:

%e +--+--+

%e |

%e +--+ +

%e | | |

%e + +--+

%e is the same as the second one in the row above after a 90-degree rotation.

%e All paths starting E are the same as the corresponding ones starting N after reflection in the forward diagonal.

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

%K nonn,hard,walk,more,changed

%O 1,3

%A _Lars Blomberg_, Jun 10 2023

%E a(1) added by _N. J. A. Sloane_, Jun 10 2023

%E a(8)-a(9) from _Martin Ehrenstein_, Jul 08 2023