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

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,5

Comments

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.

Links

Table of n, a(n) for n=2..46.

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

Formula

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

Example

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.

Prog

(Python)
# 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 += 1
     run(1, 0, 2)
     return counter
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)

Crossrefs

Cf. A003763 (bisection of main diagonal), A222200 (subdiagonal), A006864, A006865, A270273.

Sequence in context: A175474 A271877 A021387 * A127508 A244814 A090185

Adjacent sequences: A321169 A321170 A321171 * A321173 A321174 A321175

Keyword

nonn,tabl

Author

Robert FERREOL, Jan 10 2019

Extensions

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

Status

approved