A003763 Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.

1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106

Offset: 1

Author

Jeffrey Shallit, Feb 14 2002

Keywords

• nonn
• walk

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

Examples

			a(1) = 1 because there is only one such path visiting all nodes of a square.
		

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. [Broken link?]
• 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.
• Index entries for sequences related to graphs, Hamiltonian.

Crossrefs

Other enumerations of Hamiltonian cycles on a square grid: A120443, A140519, A140521, A222200, A222201.

Formula

a(n) = A321172(2n,2n). - Robert FERREOL, Apr 01 2019

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