VOOZH about

URL: https://oeis.org/A003763

⇱ A003763 - OEIS

login
A003763
Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.
45
1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106
OFFSET
1,2
COMMENTS
Orientation of the path is not important; you can start going either clockwise or counterclockwise.
The number is zero for a 2n+1 X 2n+1 grid (but see A222200).
These are also called "closed rook tours".
REFERENCES
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..13 (first 11 terms from Artem M. Karavaev, Sep 29 2010; a(12) and a(13) from Pettersson, 2014, added by N. J. A. Sloane, Jun 05 2015)
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
Artem M. Karavaev, Hamilton Cycles.
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015.
A. Pönitz, Computing invariants in graphs of small bandwidth, Mathematics in Computers and Simulation, 49(1999), 179-191.
A. Pönitz, Über eine Methode zur Konstruktion... PhD Thesis (2004) C.3.
T. G. Schmalz, G. E. Hite and D. J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A 17 (1984), 445-453.
N. J. A. Sloane, Illustration of a(2) = 6.
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles. [Backup copy of top page only, on the Internet Archive]
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.
FORMULA
a(n) = A321172(2n,2n). - Robert FERREOL, Apr 01 2019
EXAMPLE
a(1) = 1 because there is only one such path visiting all nodes of a square.
CROSSREFS
Other enumerations of Hamiltonian cycles on a square grid: A120443, A140519, A140521, A222200, A222201.
Sequence in context: A004806 A282233 A125536 * A179853 A268043 A190351
KEYWORD
nonn,walk
AUTHOR
Jeffrey Shallit, Feb 14 2002
EXTENSIONS
Two more terms from Andre Poenitz [André Pönitz] and Peter Tittmann (poenitz(AT)htwm.de), Mar 03 2003
a(8) from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 21 2006
a(9) and a(10) from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007
STATUS
approved