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

%I #82 Feb 15 2021 18:57:25

%S 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,

%T 32675,301384,4638576,1,0,596,0,175294,0,49483138,0,1,16,1517,18684,

%U 1024028,17066492,681728204,13916993782,467260456608

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

%C Orientation of the path is not important; you can start going either clockwise or counterclockwise. Paths related by symmetries are considered distinct.

%C 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).

%C These cycles are also called "closed non-intersecting rook's tours" on m X n chess board.

%H Robert Ferréol, <a href="/A321172/a321172.gif">The T(4,5)=14 hamiltonian cycles on 4 X 5 square grid of points</a>; the T(5,6) = 154 cycles on 5 X 6 grid <a href="/A321172/a321172_1.gif">are reduced to 44 different forms</a>.

%H Germain Kreweras, <a href="https://doi.org/10.1016/0195-6698(92)90005-K">Dénombrement des cycles hamiltoniens dans un rectangle quadrillé</a>, European Journal of Combinatorics, Volume 13, Issue 6 (1992), page 476.

%H Robert Stoyan and Volker Strehl, <a href="https://www.emis.de/journals/SLC/wpapers/s34erlangen.html">Enumeration of Hamiltonian Circuits in Rectangular Grids</a>, Séminaire Lotharingien de Combinatoire, B34f (1995), 21 pp.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%F T(m,n) = T(n,m).

%F T(2m+1,2n+1) = 0.

%F T(2n,2n) = A003763(n).

%F T(n,n+1) = T(n+1,n) = A222200(n).

%F G. functions , G_m(x)=Sum {n>=0} T(m,n-2)*x^n after Stoyan's link p. 18 :

%F G_2(x) = 1/(1-x) = 1+x+x^2+...

%F G_3(x) = 1/(1-2*x^2) = 1+2*x^2+4*x^4+...

%F G_4(x) = 1/(1-2*x-2*x^2+2*x^3-x^4) = 1+2*x+6*x^2+...

%F G_5(x) = (1+3*x^2)/(1-11*x^2-2*x^6) = 1+14*x^2+154*x^4+...

%e T(5,4)=14 is illustrated in the links above.

%e Table starts:

%e =================================================================

%e m\n| 2 3 4 5 6 7 8

%e ---|-------------------------------------------------------------

%e 2 | 1 1 1 1 1 1 1

%e 3 | 1 0 2 0 4 0 8

%e 4 | 1 2 6 14 37 92 236

%e 5 | 1 0 14 0 154 0 1696

%e 6 | 1 4 37 154 1072 5320 32675

%e 7 | 1 0 92 0 5320 0 301384

%e 8 | 1 8 236 1696 32675 301384 4638576

%e The table is symmetric, so it is completely described by its lower-left half.

%o (Python)

%o # Program due to Laurent Jouhet-Reverdy

%o def cycle(m, n):

%o if (m%2==1 and n%2==1): return 0

%o grid = [[0]*n for _ in range(m)]

%o grid[0][0] = 1; grid[1][0] = 1

%o counter = 0; stop = m*n-1

%o def run(i, j, nb_points):

%o for ni, nj in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)] :

%o if 0<=ni<=m-1 and 0<=nj<=n-1 and grid[ni][nj]==0 and (ni,nj)!=(0,1):

%o grid[ni][nj] = 1

%o run(ni, nj, nb_points+1)

%o grid[ni][nj] = 0

%o elif (ni,nj)==(0,1) and nb_points==stop:

%o counter += 1

%o run(1, 0, 2)

%o return counter

%o L=[];n=7#maximum for a time < 1 mn

%o for i in range(2,n):

%o for j in range(2,i+1):

%o L.append(cycle(i,j))

%o print(L)

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

%K nonn,tabl

%O 2,5

%A _Robert FERREOL_, Jan 10 2019

%E More terms from _Pontus von Brömssen_, Feb 15 2021