|
%I #90 Oct 29 2023 10:50:55
%S 1,6,1072,4638576,467260456608,1076226888605605706,
%T 56126499620491437281263608,65882516522625836326159786165530572,
%U 1733926377888966183927790794055670829347983946,1020460427390768793543026965678152831571073052662428097106
%N Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.
%C Orientation of the path is not important; you can start going either clockwise or counterclockwise.
%C The number is zero for a 2n+1 X 2n+1 grid (but see A222200).
%C These are also called "closed rook tours".
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H N. J. A. Sloane, <a href="/A003763/b003763.txt">Table of n, a(n) for n = 1..13</a> (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)
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H J. L. Jacobsen, <a href="http://dx.doi.org/10.1088/1751-8113/40/49/003">Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions</a>, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
%H Artem M. Karavaev, <a href="https://web.archive.org/web/20161024010518/http://flowproblem.ru/cycles/hamilton-cycles">Hamilton Cycles</a>.
%H Ville H. Pettersson, <a href="https://doi.org/10.37236/4510">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
%H Ville Pettersson, <a href="https://aaltodoc.aalto.fi/handle/123456789/17688">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Dissertation, Aalto, Finland, 2015.
%H A. Pönitz, <a href="http://dx.doi.org/10.1016/S0378-4754(99)00052-X">Computing invariants in graphs of small bandwidth</a>, Mathematics in Computers and Simulation, 49(1999), 179-191.
%H A. Pönitz, <a href="https://tubaf.qucosa.de/api/qucosa%3A22459/attachment/ATT-0/">Über eine Methode zur Konstruktion...</a> PhD Thesis (2004) C.3.
%H T. G. Schmalz, G. E. Hite and D. J. Klein, <a href="http://dx.doi.org/10.1088/0305-4470/17/2/029">Compact self-avoiding circuits on two-dimensional lattices</a>, J. Phys. A 17 (1984), 445-453.
%H N. J. A. Sloane, <a href="/A003763/a003763.jpg">Illustration of a(2) = 6</a>.
%H Peter Tittmann, <a href="http://www.htwm.de/~peter/research/enumeration.html">Enumeration in graphs: counting Hamiltonian cycles</a>. [Broken link?]
%H Peter Tittmann, <a href="http://web.archive.org/web/20101127064650/https://www.staff.hs-mittweida.de/~peter/research/enumeration.html">Enumeration in graphs: counting Hamiltonian cycles</a>. [Backup copy of top page only, on the Internet Archive]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>.
%H Ed Wynn, <a href="http://arxiv.org/abs/1402.0545">Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs</a>, arXiv preprint arXiv:1402.0545 [math.CO], 2014.
%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>.
%F a(n) = A321172(2n,2n). - _Robert FERREOL_, Apr 01 2019
%e a(1) = 1 because there is only one such path visiting all nodes of a square.
%Y Other enumerations of Hamiltonian cycles on a square grid: A120443, A140519, A140521, A222200, A222201.
%K nonn,walk
%O 1,2
%A _Jeffrey Shallit_, Feb 14 2002
%E Two more terms from Andre Poenitz [André Pönitz] and Peter Tittmann (poenitz(AT)htwm.de), Mar 03 2003
%E a(8) from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 21 2006
%E a(9) and a(10) from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007
| 