A222200 -id:A222200 - 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

A321172 Triangle read by rows: T(m,n) = number of Hamiltonian cycles on m X n grid of points (m >= 2, 2 <= n <= m).

Original entry on oeis.org

1, 1, 0, 1, 2, 6, 1, 0, 14, 0, 1, 4, 37, 154, 1072, 1, 0, 92, 0, 5320, 0, 1, 8, 236, 1696, 32675, 301384, 4638576, 1, 0, 596, 0, 175294, 0, 49483138, 0, 1, 16, 1517, 18684, 1024028, 17066492, 681728204, 13916993782, 467260456608

Offset: 2

Robert FERREOL, Jan 10 2019

Orientation of the path is not important; you can start going either clockwise or counterclockwise. Paths related by symmetries are considered distinct.
The m X n grid of points when drawn forms a (m-1) X (n-1) rectangle of cells, so m-1 and n-1 are sometimes used as indices instead of m and n (see, e. g., Kreweras' reference below).
These cycles are also called "closed non-intersecting rook's tours" on m X n chess board.

			T(5,4)=14 is illustrated in the links above.
Table starts:
=================================================================
m\n|  2    3      4       5         6           7            8
---|-------------------------------------------------------------
2  |  1    1      1       1         1           1            1
3  |  1    0      2       0         4           0            8
4  |  1    2      6      14        37          92          236
5  |  1    0     14       0       154           0         1696
6  |  1    4     37     154      1072        5320        32675
7  |  1    0     92       0      5320           0       301384
8  |  1    8    236    1696     32675      301384      4638576
The table is symmetric, so it is completely described by its lower-left half.

Huaide Cheng, Rows n=2..17 of triangle, flattened
Robert Ferréol, The T(4,5)=14 hamiltonian cycles on 4 X 5 square grid of points; the T(5,6) = 154 cycles on 5 X 6 grid are reduced to 44 different forms.
Germain Kreweras, Dénombrement des cycles hamiltoniens dans un rectangle quadrillé, European Journal of Combinatorics, Volume 13, Issue 6 (1992), page 476.
Robert Stoyan and Volker Strehl, Enumeration of Hamiltonian Circuits in Rectangular Grids, Séminaire Lotharingien de Combinatoire, B34f (1995), 21 pp.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.

Row/column k=4..12 are: (with interspersed zeros for odd k): A006864, A006865, A145401, A145416, A145418, A160149, A180504, A180505, A213813.
Cf. A003763 (bisection of main diagonal), A222200 (subdiagonal), A231829, A270273, A332307.
T(n,2n) gives A333864.

# Program due to Laurent Jouhet-Reverdy
def cycle(m, n):
     if (m%2==1 and n%2==1): return 0
     grid = [[0]*n for _ in range(m)]
     grid[0][0] = 1; grid[1][0] = 1
     counter = [0]; stop = m*n-1
     def run(i, j, nb_points):
         for ni, nj in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)] :
             if  0<=ni<=m-1 and 0<=nj<=n-1 and grid[ni][nj]==0 and (ni,nj)!=(0,1):
                 grid[ni][nj] = 1
                 run(ni, nj, nb_points+1)
                 grid[ni][nj] = 0
             elif (ni,nj)==(0,1) and nb_points==stop:
                 counter[0] += 1
     run(1, 0, 2)
     return counter[0]
L=[];n=7#maximum for a time < 1 mn
for i in range(2,n):
    for j in range(2,i+1):
       L.append(cycle(i,j))
print(L)

T(m,n) = T(n,m).
T(2m+1,2n+1) = 0.
T(2n,2n) = A003763(n).
T(n,n+1) = T(n+1,n) = A222200(n).
G. functions , G_m(x)=Sum {n>=0} T(m,n-2)*x^n after Stoyan's link p. 18 :
G_2(x) = 1/(1-x) = 1+x+x^2+...
G_3(x) = 1/(1-2*x^2) = 1+2*x^2+4*x^4+...
G_4(x) = 1/(1-2*x-2*x^2+2*x^3-x^4) = 1+2*x+6*x^2+...
G_5(x) = (1+3*x^2)/(1-11*x^2-2*x^6) = 1+14*x^2+154*x^4+...

More terms from Pontus von Brömssen, Feb 15 2021

A222201 Write n=3i+j, 0<=j<3; a(n) = number of Hamiltonian cycles on square grid of points of size 2i+2 X 2i+2 (if j=0), 2i+2 X 2i+3 (j=1) or 2i+3 X 2i+4 (j=2).

Original entry on oeis.org

1, 1, 2, 6, 14, 154, 1072, 5320, 301384, 4638576, 49483138, 13916993782, 467260456608, 10754797724124, 14746957510647992, 1076226888605605706, 53540340738182687296, 354282765498796010420944, 56126499620491437281263608, 6040964455632840415885507728, 191678405883294971709423926242394, 65882516522625836326159786165530572

Offset: 0

N. J. A. Sloane, Feb 14 2013

nonn

An interleaving of A003763 and A222200.

Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Broken link?]
Peter Tittman, Illustration of a(4) = 14 [Taken from preceding link]
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Backup copy of top page only, on the Internet Archive]
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A222200.

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

A321172 Triangle read by rows: T(m,n) = number of Hamiltonian cycles on m X n grid of points (m >= 2, 2 <= n <= m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A222201 Write n=3i+j, 0<=j<3; a(n) = number of Hamiltonian cycles on square grid of points of size 2i+2 X 2i+2 (if j=0), 2i+2 X 2i+3 (j=1) or 2i+3 X 2i+4 (j=2).

Views

Author

Keywords

Comments

Links

Crossrefs