

A003763


Number of Hamiltonian cycles on 2n X 2n square grid of points.


30



1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106
(list;
graph;
refs;
listen;
history;
text;
internal format)



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), 129154.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015; https://aaltodoc.aalto.fi/bitstream/handle/123456789/17688/isbn9789526063652.pdf?sequence=1


LINKS

Artem M. Karavaev and 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), 129154.
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 1466714678
Artem M. Karavaev, Hamilton Cycles.
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
A. Pönitz, Computing invariants in graphs of small bandwidth, Mathematics in Computers and Simulation, 49(1999), 179191
T. G. Schmalz, G. E. Hite and D. J. Klein, Compact selfavoiding circuits on twodimensional lattices, J. Phys. A 17 (1984), 445453.
N. J. A. Sloane, Illustration of a(2) = 6
Peter Tittmann, Enumeration in graphs: counting Hamilton cycles
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545, 2014
Index entries for sequences related to graphs, Hamiltonian


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: A159865 A004806 A125536 * A179853 A268043 A190351
Adjacent sequences: A003760 A003761 A003762 * A003764 A003765 A003766


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)upsud.fr), Dec 12 2007


STATUS

approved



