A140521 -id:A140521 - cp's OEIS frontend

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

Jeffrey Shallit, Feb 14 2002

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

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

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

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.

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

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

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

A209077 Number of Hamiltonian circuits (or self-avoiding rook's tours) on a 2n X 2n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Original entry on oeis.org

1, 2, 149, 580717, 58407763266, 134528361351329451, 7015812452562871283559623, 8235314565328229583744138065519908, 216740797236120772990979350241355889872437894, 127557553423846099192878370713500303677609606263171680998

Offset: 1

N. J. A. Sloane, Mar 04 2012

nonn

Christopher Hunt Gribble confirms a(3), and reports that there are 121 figures with group of order 1, 24 with group of order 2, and 4 with group of order 4. Then 121*(8/1) + 24*(8/2) + 4*(8/4) = 1072 = A003763(3), 121 + 24 + 4 = 149 = a(3). - N. J. A. Sloane, Feb 22 2013

Jon Wild, Posting to Sequence Fans Mailing List, Dec 10 2011.

Mathoverflow, Counting Hamiltonian cycles in n x n square grid, question asked by Joseph O'Rourke, Jul 25 2018.
Jon Wild, Illustration of a(3)
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv:1402.0545 [math.CO], 3 Feb 2014.
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A120443, A140519, A140521.

a(5)-a(10) from Ed Wynn, Feb 05 2014

A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

Original entry on oeis.org

1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418

Offset: 1

Don Knuth, Jul 26 2008

Or, number of Hamiltonian cycles in the graph P_n X P_n (strong product of two paths of length n-1).
If the direction of the tour is to be taken into account, the numbers for n > 1 must be multiplied by 2 (see A140521).
Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

D. E. Knuth, The Art of Computer Programming, Section 7.1.4, in preparation.

N. J. A. Sloane, Table of n, a(n) for n = 1..16 [From Pettersson 2014]
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.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A001230, A140521.

New name from Eric W. Weisstein, May 06 2019

A158651 Number of directed Hamiltonian paths on the n X n king graph.

Original entry on oeis.org

1, 24, 784, 343184, 729237344, 13089822163800, 1659110130720710584, 1635069460917798701270872, 12308784500036123518164726610224, 721833220650131890343295654587745095696, 330596986686626406483380599328509951896788808144

Offset: 1

Eric W. Weisstein, Mar 23 2009

Number of open directed king's tours on the n X n board.

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A096969, A137891, A140521.

a(5) from Max Alekseyev, May 03 2009

a(6)-a(11) from Andrew Howroyd, Nov 15 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A209077 Number of Hamiltonian circuits (or self-avoiding rook's tours) on a 2n X 2n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A158651 Number of directed Hamiltonian paths on the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions