A180504 -id:A180504 - cp's OEIS frontend

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

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

A180505 Number of Hamiltonian cycles in P_11 X P_2n.

Original entry on oeis.org

1, 3846, 5668692, 7837276902, 10754797724124, 14746957510647992, 20223692320200140940, 27738606105535271640888, 38049128385426605236700966, 52194036750499722755908743018, 71598455565101470929617326988084, 98217523834843365306426848969040826, 134733398926676359394934062807293332148

Offset: 1

Artem M. Karavaev, Sep 09 2010

nonn

The linear recurrence for this sequence has order 671. It is too large to be posted here.

Huaide Cheng, Table of n, a(n) for n = 1..319 (terms 1..50 Seiichi Manyama)
Flow Problem, Hamilton Cycles (see Maple worksheet).
Index entries for linear recurrences with constant coefficients, order 671.

Cf. A180504, A321172.

a(11)-a(13) from Seiichi Manyama, Mar 29 2020

A222195 Order of linear recurrence for number of Hamiltonian cycles in the graph P_n X P_{2k} (n odd) or P_n X P_k (n even), as a function of k.

Original entry on oeis.org

1, 4, 3, 14, 18, 66, 104, 346, 671, 2086, 4479, 13523

Offset: 3

N. J. A. Sloane, Feb 14 2013

Artem M. Karavaev, Hamilton Cycles

Cf. A006864, A006865, A145401, A145416, A145418, A160149, A180504, A180505.

A339962 Number of Hamiltonian circuits within parallelograms of size 10 X n on the triangular lattice.

Original entry on oeis.org

1, 18980, 8782833, 4190083085, 2848083212818, 1738936046774850, 1033232532941136255, 621423541447699842468, 373334515946952014204102, 223802065032649969887333948, 134170413630013820290109500226, 80436114451156297907062202392494, 48216986287603185632341666866663007

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. (a(n) is equal to h9(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 10 of A339849.

Cf. A180504.

cp's OEIS Frontend

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

A180505 Number of Hamiltonian cycles in P_11 X P_2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A222195 Order of linear recurrence for number of Hamiltonian cycles in the graph P_n X P_{2k} (n odd) or P_n X P_k (n even), as a function of k.

Views

Author

Keywords

Links

Crossrefs

A339962 Number of Hamiltonian circuits within parallelograms of size 10 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs