The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003763 Number of (undirected) Hamiltonian cycles on 2n X 2n square grid of points. 42


%S 1,6,1072,4638576,467260456608,1076226888605605706,

%T 56126499620491437281263608,65882516522625836326159786165530572,

%U 1733926377888966183927790794055670829347983946,1020460427390768793543026965678152831571073052662428097106

%N Number of (undirected) Hamiltonian cycles on 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 Artem M. Karavaev and 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="http://flowproblem.ru/cycles/hamilton-cycles">Hamilton Cycles</a>.

%H Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">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&ouml;nitz, <a href="http://www.qucosa.de/fileadmin/data/qucosa/documents/2080/MathematikPXnitzAndrX756952.pdf">&Uuml;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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 2 16:47 EDT 2020. Contains 335404 sequences. (Running on oeis4.)