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

A339120 Number of cycles in the grid graph P_8 X P_n.

Original entry on oeis.org

28, 1664, 114069, 5948291, 279285399, 12947640143, 603841648931, 28251882697663, 1322310119854705, 61875355046353061, 2895006802805407868, 135448608195945754204, 6337277838067727854392, 296505504331623399871908, 13872765058478362509835979, 649072483984291902586660423

Offset: 2

Seiichi Manyama, Nov 24 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 2..200
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A140517, A145418, A231829.

Terms a(10) and beyond from Andrew Howroyd, Dec 08 2020

A339960 Number of Hamiltonian circuits within parallelograms of size 8 X n on the triangular lattice.

Original entry on oeis.org

1, 1676, 183521, 20842802, 3061629439, 418172485806, 56203566442908, 7621726574570613, 1033232532941136255, 139934009951521872490, 18955155770535463735959, 2567688102114635009977537, 347811042296785583958285788, 47113523803568895604053871759, 6381875340326645360658645942215

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..100
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 h7(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 8 of A339849.

Cf. A145418.

# Using graphillion
from graphillion import GraphSet
def make_T_nk(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339960(n):
    return A339849(8, n)
print([A339960(n) for n in range(2, 8)])

A005391 Number of Hamiltonian circuits on 2n X 8 rectangle.

Original entry on oeis.org

1, 236, 32675, 4638576, 681728204, 102283239429, 15513067188008, 2365714170297014, 361749878496079778, 55391169255983979555, 8487168277379774266411, 1300854247070195164448395, 199418506963731877069653608, 30572953033472980838613625389

Offset: 1

N. J. A. Sloane

nonn

Bisection (even part) of A145418. - Joerg Arndt, Feb 05 2014

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 and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Wikipedia, Hamiltonian circuit

More terms from Alois P. Heinz, Feb 05 2014

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

A339120 Number of cycles in the grid graph P_8 X P_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A339960 Number of Hamiltonian circuits within parallelograms of size 8 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A005391 Number of Hamiltonian circuits on 2n X 8 rectangle.

Views

Author

Keywords

Comments

References

Links

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