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

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

Original entry on oeis.org

48, 1344, 23580, 3273360, 257165468, 171785923808, 61997157648756, 196554899918485160

Offset: 3

N. J. A. Sloane, Feb 14 2013

C_n X C_n is also known as the (n,n)-torus grid graph.

Artem M. Karavaev, Hamilton Cycles.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270273, A003763, A222197, A268838, A222198, A193153, A270247.

Table[Length[FindHamiltonianCycle[GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], All]], {n, 3, 6}] (* Eric W. Weisstein, Dec 16 2023 *)

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

Original entry on oeis.org

1, 1, 4, 1, 3, 4, 1, 6, 6, 4, 1, 5, 22, 12, 4, 1, 8, 30, 82, 24, 4, 1, 7, 86, 160, 306, 48, 4, 1, 10, 126, 776, 850, 1142, 96, 4, 1, 9, 318, 1484, 7010, 4520, 4262, 192, 4, 1, 12, 510, 6114, 18452, 63674, 24040, 15906, 384, 4, 1, 11, 1182, 12348, 126426, 229698, 578090, 127860, 59362, 768, 4

Offset: 1

Andrew Howroyd, Feb 18 2025

The case for P_n X C_2 is determined using a double edge for C_2.

			Array begins:
=========================================================
n\k | 2   3     4      5       6        7          8 ...
----+---------------------------------------------------
  1 | 1   1     1      1       1        1          1 ...
  2 | 4   3     6      5       8        7         10 ...
  3 | 4   6    22     30      86      126        318 ...
  4 | 4  12    82    160     776     1484       6114 ...
  5 | 4  24   306    850    7010    18452     126426 ...
  6 | 4  48  1142   4520   63674   229698    2588218 ...
  7 | 4  96  4262  24040  578090  2861964   53055038 ...
  8 | 4 192 15906 127860 5247824 35663964 1087362018 ...
   ...

Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.

Columns 2..12 are A123932(n-1), A003945(n-1), A003699, A003731, A180582, A180583, A180584, A180585, A180586, A180587, A180588.
Rows 1..2 are A000012, A103889(n+1).
Cf. A222196 (order of recurrences), A222197 (main diagonal), A270273, A321172.

A124349 Numbers of directed Hamiltonian cycles on the n-prism graph.

Original entry on oeis.org

6, 12, 10, 16, 14, 20, 18, 24, 22, 28, 26, 32, 30, 36, 34, 40, 38, 44, 42, 48, 46, 52, 50, 56, 54, 60, 58, 64, 62, 68, 66, 72, 70, 76, 74, 80, 78, 84, 82, 88, 86, 92, 90, 96, 94, 100, 98, 104, 102, 108, 106, 112, 110, 116, 114, 120, 118, 124, 122, 128, 126, 132, 130

Offset: 3

Eric W. Weisstein, Oct 26 2006

Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Prism Graph.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A014681, A124350, A270273.

[2*n+(1-(n mod 2))*4: n in [3..80]]; // Vincenzo Librandi, Jan 26 2016

seq( 2*n + (1-(n mod 2))*4, n=3..100); # Robert Israel, Mar 14 2016

Table[2 n + (1 - Mod[n, 2]) 4, {n, 3, 100}] (* Vincenzo Librandi, Jan 26 2016 *)

Vec(2*x^3*(3+3*x-4*x^2)/((1-x)^2*(1+x)) + O(x^100)) \\ Altug Alkan, Mar 14 2016

a(n) = 2*n + (1-(n mod 2))*4.
From Colin Barker, Aug 22 2012: (Start)
a(n) = a(n-1)+a(n-2)-a(n-3).
G.f.: 2*x^3*(3+3*x-4*x^2)/((1-x)^2*(1+x)). (End)
a(n) = 2*A014681(n+1). - R. J. Mathar, Jan 25 2016
E.g.f.: 2*(2 + x)*cosh(x) + 2*x*sinh(x) - 2*(2 + x + 2*x^2). - Stefano Spezia, Jan 28 2024

Name clarified by Andrew Howroyd, Mar 14 2016

A194952 Number of Hamiltonian cycles in C_3 X C_n.

Original entry on oeis.org

48, 126, 390, 1014, 2982, 8094, 23646, 66726, 196086, 568302, 1682382, 4954998, 14750310, 43833150, 130942398, 390959430, 1170256854, 3502513038, 10495480494, 31450265622, 94296270918, 282731526366

Offset: 3

Artem M. Karavaev, Sep 06 2011

All terms of this sequence are divisible by 6 (which follows from the g.f.).

Vincenzo Librandi, Table of n, a(n) for n = 3..2000
Artem M. Karavaev, Hamilton Cycles page
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (5,-1,-25,26,20,-24).

Row 3 of A270273.

[3^n + 3/4*n*2^n + (2^n-(-2)^n)/2 + (-1)^n - 4: n in [3..40]]; // Vincenzo Librandi, Sep 19 2011

C3xCn := n->3^n+3/4*n*2^n+(2^n-(-2)^n)/2+(-1)^n-4:seq(C3xCn(n),n=3..16);

a(n)=([0,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; -24,20,26,-25,-1,5]^(n-3)*[48;126;390;1014;2982;8094])[1,1] \\ Charles R Greathouse IV, Jul 08 2024

# Using graphillion
from graphillion import GraphSet
def make_CnXCk(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))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
        grids.append((i + k - 1, i))
    return grids
def A194952(n):
    universe = make_CnXCk(n, 3)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A194952(n) for n in range(3, 30)])  # Seiichi Manyama, Nov 22 2020

a(n) = 3^n + 3/4*n*2^n + (2^n-(-2)^n)/2 + (-1)^n - 4, n>=3.
a(n) = 5*a(n-1)-a(n-2)-25*a(n-3)+26*a(n-4)+20*a(n-5)-24*a(n-6), for n>=9, with a(3)=48, a(4)=126, a(5)=390, a(6)=1014, a(7)=2982, a(8)=8094.
G.f.: -6*x^3*(-8+19*x+32*x^2-65*x^3-34*x^4+48*x^5) / ( (x-1)*(3*x-1)*(2*x+1)*(1+x)*(-1+2*x)^2 ). - R. J. Mathar, Sep 18 2011

More terms from Alexander R. Povolotsky, Sep 07 2011

A358853 Number of Hamiltonian cycles in C_5 X C_n.

Original entry on oeis.org

20, 390, 2930, 23580, 145210, 1045940, 6228730, 43322370, 260600210, 1776654220, 10913989610, 73525916750, 461264468640, 3088176680560, 19722405442490, 131703577902460, 853035459491710, 5693694272274220, 37271158654667390, 248902943147007900

Offset: 2

Seiichi Manyama, Dec 03 2022

nonn

Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Row 5 of A270273.

Cf. A222199.

More terms from Ed Wynn, Jun 25 2023

A216588 Number of Hamiltonian cycles in C_4 X C_n.

Original entry on oeis.org

126, 1344, 2930, 28060, 55230, 538744, 969378, 10066228, 16284862, 186362560, 265582226, 3447630284, 4238980734, 64031790664, 66561185858, 1197008258212, 1031815027710, 22548844488592, 15830131853490, 428115681210300, 240803790623806, 8188893146929816

Offset: 3

Artem M. Karavaev, Sep 09 2012

nonn

The sequence is not monotone, although it seems to be.

It has two monotone subsequences depending on the parity of n.

Seiichi Manyama, Table of n, a(n) for n = 3..100
Artem M. Karavaev, Hamilton Cycles: Flow Problem.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Row 4 of A270273. Cf. A194952.

P := n -> (2*n+1)*cosh(2*n*arctanh(sqrt(1/3))) - (n/sqrt(3))*sinh(2*n*arctanh(sqrt(1/3))) + cos(Pi*n/2) - sin(Pi*n/2):
Q := n -> (4^n-16*3^n-4)/3+8*2^(n/2)*cos(n*arctan(sqrt(7))) + 4*2^n*cosh(2*n*arctanh(sqrt(2/3)))-2*cosh(2*n*arctanh(sqrt(1/2))):
R := n -> -2*(n+1)*(2-(-1)^n):
a := n -> expand(P(n)) + (1 - n mod 2)*expand(Q(floor(n/2))) + (n mod 2)*R(floor(n/2)):
seq(a(n),n=3..24);

a(n) = P(n) + Q(floor(n/2)) if n is even and a(n) = P(n) + R(floor(n/2)) if n is odd, where P(n) = (2*n + 1)*cosh(2*n*arctanh(sqrt(1/3))) - (n/sqrt(3))*sinh(2*n*arctanh(sqrt(1/3))) + cos(Pi*n/2) - sin(Pi*n/2), Q(n) = (4^n - 16*3^n - 4)/3 + 8*2^(n/2)*cos(n*arctan(sqrt(7))) + 4*2^n*cosh(2*n*arctanh(sqrt(2/3))) - 2*cosh(2*n*arctanh(sqrt(1/2))), R(n) = -2*(n + 1)*(2 - (-1)^n).
G.f.: -48*x^2 - 2*x - 17/3 + (1 - x)/(x^2 + 1) + 1/(6*(2*x + 1)) + (x + 1)/(x^2 - 2*x - 1) - 1/((x - 1)^2) + (8 - 4*x^2)/(2*x^4 - x^2 + 1) + (-16 + 62*x)/(x^2 - 4*x + 1)^2 - 2/3/(x + 1) + 1/((x + 1)^2) + (17 + 3*x)/(x^2 - 4*x + 1) + (-2 - 4*x)/(2*x^2 - 4*x - 1) + 2/3/(x - 1) - 1/(6*(2*x - 1)) + (1 - x)/(x^2 + 2*x - 1) + (-2 + 4*x)/(2*x^2 + 4*x - 1) + 16/3/(3*x^2 - 1) + 2*x/(x^2 + 1)^2.
Asympt.: a(n) ~ 2*(2 + sqrt(6))^n if n is even and
a(n) ~ ((1 - 1/(2*sqrt(3)))*n + 1/2)*(2 + sqrt(3))^n if n is odd.

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

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A124349 Numbers of directed Hamiltonian cycles on the n-prism graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A194952 Number of Hamiltonian cycles in C_3 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

PARI

Python

Formula

Extensions

A358853 Number of Hamiltonian cycles in C_5 X C_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A216588 Number of Hamiltonian cycles in C_4 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula