A194952 -id:A194952 - cp's OEIS frontend

A270273 Array read by antidiagonals: T(n,m) = number of Hamiltonian cycles in C_n X C_m.

0, 0, 0, 1, 1, 1, 1, 3, 3, 1, 1, 6, 48, 6, 1, 1, 5, 126, 126, 5, 1, 1, 8, 390, 1344, 390, 8, 1, 1, 7, 1014, 2930, 2930, 1014, 7, 1, 1, 10, 2982, 28060, 23580, 28060, 2982, 10, 1, 1, 9, 8094, 55230, 145210, 145210, 55230, 8094, 9, 1

Offset: 1

Andrew Howroyd, Mar 14 2016

			The start of the sequence as table:
  0 0    1     1       1        1         1 ...
  0 1    3     6       5        8         7 ...
  1 3   48   126     390     1014      2982 ...
  1 6  126  1344    2930    28060     55230 ...
  1 5  390  2930   23580   145210   1045940 ...
  1 8 1014 28060  145210  3273360  16111928 ...
  1 7 2982 55230 1045940 16111928 257165468 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..191
Artem M. Karavaev, Hamilton Cycles
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Row n=3-5 give: A194952, A216588, A358853.

Main diagonal gives A222199.

T(n,2) = A124349(n) / 2.

A339074 Number of (undirected) cycles in the graph C_3 X C_n.

Original entry on oeis.org

312, 1531, 7298, 35205, 174268, 885719, 4601982, 24306577, 129851384, 698930787, 3780126106, 20505863069, 111441343860, 606312668335, 3300926292470, 17978225967081, 97939845566896, 533619551723963, 2907629293865874, 15844069824657013, 86338863686763692, 470492593924667271

Offset: 3

Seiichi Manyama, Nov 22 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 3..500
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Cf. A194952, A296527, A339075.

# 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 A339074(n):
    universe = make_CnXCk(n, 3)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339074(n) for n in range(3, 30)])

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

A270273 Array read by antidiagonals: T(n,m) = number of Hamiltonian cycles in C_n X C_m.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A339074 Number of (undirected) cycles in the graph C_3 X C_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A216588 Number of Hamiltonian cycles in C_4 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula