Artem M. Karavaev - cp's OEIS frontend

A216588 Number of Hamiltonian cycles in C_4 X C_n.

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.

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

A181584 Number of cycles of length (2n+1)^2-1 on 2n+1 X 2n+1 square grid.

Original entry on oeis.org

5, 226, 255088, 6663430912, 3916162476483538, 51249820944023435573470, 14870957102232406137455708164254, 95494789899510664733921727510895952184006

Offset: 1

Artem M. Karavaev, Oct 31 2010

nonn

This sequence is a way to extend the sequence A003763 in case of grids with odd number of nodes: a(n) is the number of cycles in odd-side square lattice with maximum possible length.

Artem M. Karavaev, Table of n, a(n) for n=1..10
a(1)-a(10) were obtained during a small programming contest (in Russian).
Artem M. Karavaev, Prehamilton Cycles page
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763.

A180582 Number of Hamiltonian cycles in C_6 X P_n.

Original entry on oeis.org

1, 8, 86, 776, 7010, 63674, 578090, 5247824, 47640092, 432480632, 3926091512, 35641352528, 323554871864, 2937255393440, 26664624744320, 242063463190976, 2197470272854016, 19948799940346880, 181096701955896896, 1644009442040416928, 14924441010395894048, 135485194778650515104

Offset: 1

Artem M. Karavaev, Sep 10 2010

Seiichi Manyama, Table of n, a(n) for n = 1..500
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, signature (9,0,10,-28,-36,-32,-12).

Column k=6 of A359855.

Cf. A003699, A003731, A180583, A180584, A180585, A180586, A180587, A180588.

a(n) = if(n<1, 0, if(n<=8, [1, 8, 86, 776, 7010, 63674, 578090, 5247824][n], -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) ) );
/* Joerg Arndt, Sep 02 2012 */

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(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))
    return grids
def A180582(n):
    universe = make_CnXPk(6, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A180582(n) for n in range(1, 30)])  # Seiichi Manyama, Nov 25 2020

a(n) = -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) for n > 8.

G.f.: x*(x +1)*(6*x^6 -14*x^5 -2*x^4 -24*x^3 +16*x^2 -2*x +1)/(12*x^7 +32*x^6 +36*x^5 +28*x^4 -10*x^3 -9*x +1). - Colin Barker, Sep 01 2012

A180583 Number of Hamiltonian cycles in C_7 X P_n.

Original entry on oeis.org

1, 7, 126, 1484, 18452, 229698, 2861964, 35663964, 444486280, 5539931796, 69048910000, 860620499760, 10726732430288, 133697577587000, 1666401898058352, 20769976722986288, 258876295158900832, 3226625529605854320, 40216553455854426560, 501257787787122948736

Offset: 1

Artem M. Karavaev, Sep 10 2010

Andrew Howroyd, Table of n, a(n) for n = 1..500
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, signature (12,18,-112,-440,-772,-196,2064,3724,2040,496,128,-16).

Column k=7 of A359855.

Cf. A003699, A003731, A180582, A180584, A180585, A180586, A180587, A180588.

a(n) = -16a(n-12) + 128a(n-11) + 496a(n-10) + 2040a(n-9) + 3724a(n-8) + 2064a(n-7) - 196a(n-6) - 772a(n-5) - 440a(n-4) - 112a(n-3) + 18a(n-2) + 12a(n-1) for n > 13.

G.f.: x*(16*x^12 -16*x^11 +8*x^10 -192*x^9 +588*x^8 +1996*x^7 +700*x^6 -474*x^5 -400*x^4 -42*x^3 +24*x^2 -5*x +1)/(16*x^12 -128*x^11 -496*x^10 -2040*x^9 -3724*x^8 -2064*x^7 +196*x^6 +772*x^5 +440*x^4 +112*x^3 -18*x^2 -12*x +1). - Colin Barker, Sep 01 2012

a(18) onwards from Andrew Howroyd, Feb 18 2025

A180585 Number of Hamiltonian cycles in C_9 X P_n.

Original entry on oeis.org

1, 9, 510, 12348, 351258, 9806292, 276018090, 7769376972, 218915964618, 6169925169414, 173923080282474, 4903042542453720, 138226113213225360, 3896923927019062734, 109864493967924549384, 3097380080814655131414, 87323767337933601800838, 2461902328199084994926838

Offset: 1

Artem M. Karavaev, Sep 10 2010

Andrew Howroyd, Table of n, a(n) for n = 1..200
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, order 51.

Column k=9 of A359855.

a(n) = -188416a(n-51) + 835584a(n-50) + 7955456a(n-49) - 41793024a(n-48) -
33238528a(n-47) + 334600192a(n-46) - 1276157184a(n-45) + 2732681344a(n-44) -
2618432768a(n-43) - 5036989056a(n-42) + 11060535424a(n-41) + 27959018048a(n-40) -
52440361440a(n-39) - 37908518240a(n-38) + 74330191136a(n-37) + 59186108112a(n-36) -
68887152928a(n-35) - 33605932304a(n-34) + 43670159120a(n-33) + 48309187400a(n-32) +
33949381128a(n-31) + 12462888472a(n-30) - 88313767808a(n-29) - 107865096688a(n-28) +
20762733116a(n-27) + 153311805598a(n-26) + 152573320432a(n-25) + 38397703554a(n-24) -
70575876534a(n-23) - 117036064104a(n-22) - 90546530362a(n-21) - 20062310737a(n-20) +
30892900555a(n-19) + 30318783786a(n-18) + 6586175756a(n-17) - 5975151103a(n-16) -
4972136691a(n-15) - 2026783228a(n-14) - 1418765189a(n-13) - 1239197497a(n-12) -
576571223a(n-11) - 60031321a(n-10) + 63704924a(n-9) + 32475252a(n-8) + 6586040a(n-7) +
334567a(n-6) - 152710a(n-5) - 38447a(n-4) - 2238a(n-3) + 280a(n-2) + 23a(n-1), n>52.

a(17) onwards from Andrew Howroyd, Feb 18 2025

A180586 Number of Hamiltonian cycles in C_10 X P_n.

Original entry on oeis.org

1, 12, 1182, 45502, 2127332, 95718442, 4343656672, 196769260362, 8917775068522, 404126474166012, 18314237688963002, 829962636335203152, 37612209746663052792, 1704508129504662739932, 77244815889633863270612, 3500576762912651494559832, 158638966340047716575123082

Offset: 1

Artem M. Karavaev, Sep 10 2010

nonn

The linear recurrence for this sequence has order 74. For aesthetic reasons we don't post it here.

Andrew Howroyd, Table of n, a(n) for n = 1..200
You can download Maple worksheet with the recurrence from our Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, order 74.

Column k=10 of A359855.

a(16) onwards from Andrew Howroyd, Feb 18 2025

A180587 Number of Hamiltonian cycles in C_11 X P_n.

Original entry on oeis.org

1, 11, 2046, 97328, 6355404, 387822094, 24320491316, 1519170232976, 95249624584400, 5973677282007402, 374905251599545986, 23534073657511178476, 1477568095192517655932, 92775355905853945839438, 5825578147023937709240306, 365810849961625116513720948, 22971031488025813312501357724

Offset: 1

Artem M. Karavaev, Sep 10 2010

nonn

The linear recurrence for this sequence has order 246. For aesthetic reasons we don't post it here.

Andrew Howroyd, Table of n, a(n) for n = 1..200
You can download Maple worksheet with the recurrence from our Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, order 246.

Column k=11 of A359855.

a(15) onwards from Andrew Howroyd, Feb 18 2025

A180588 Number of Hamiltonian cycles in C_12 X P_n.

Original entry on oeis.org

1, 14, 4478, 330838, 35085590, 3411202430, 340632046678, 33794298241774, 3360563350227504, 334009240038242920, 33204360051870939552, 3300767481388100805696, 328127904170727818697864

Offset: 1

Artem M. Karavaev, Sep 10 2010

nonn

The linear recurrence for this sequence has order 303. For aesthetic reasons we don't post it here.

You can download Maple worksheet with the recurrence from our Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, order 303.

A180584 Number of Hamiltonian cycles in C_8 X P_n.

Original entry on oeis.org

1, 10, 318, 6114, 126426, 2588218, 53055038, 1087362018, 22286085818, 456763781330, 9361593883038, 191870363459178, 3932475321605194, 80597971743535618, 1651894168575456078, 33856364932336405826, 693902471632291156946, 14221864665640856614738, 291483951760814319838934

Offset: 1

Artem M. Karavaev, Sep 10 2010

Andrew Howroyd, Table of n, a(n) for n = 1..200
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, signature (23,-34,-345,-218,22, 2919,5041,8806,11998,5873, -1318,-4467,-11373,-3848, 584,-1018,928,-84,-72,40).

Column k=8 of A359855.

a(n) = 40a(n-20) - 72a(n-19) - 84a(n-18) + 928a(n-17) - 1018a(n-16) +
584a(n-15) - 3848a(n-14) - 11373a(n-13) - 4467a(n-12) - 1318a(n-11) +
5873a(n-10) + 11998a(n-9) + 8806a(n-8) + 5041a(n-7) + 2919a(n-6) +
22a(n-5) - 218a(n-4) - 345a(n-3) - 34a(n-2) + 23a(n-1) for n>21.
G.f.: x -2*x^2 *(5 +44*x -430*x^2 +33*x^3 +93*x^4 +1471*x^5 +4596*x^6 +6807*x^7 +8263*x^8 +2751*x^9 -2482*x^10 -5126*x^11 -4711*x^12 -2094*x^13 -1406*x^14 +450*x^15 +580*x^16 -132*x^17 +32*x^18 +40*x^19)/(-1 +23*x -34*x^2 -345*x^3 -218*x^4 +22*x^5 +2919*x^6 +5041*x^7 +8806*x^8 +11998*x^9 +5873*x^10 -1318*x^11 -4467*x^12 -11373*x^13 -3848*x^14 +584*x^15 -1018*x^16 +928*x^17 -84*x^18 -72*x^19 +40*x^20) . - R. J. Mathar, Feb 28 2025

a(17) onwards from Andrew Howroyd, Feb 18 2025

cp's OEIS Frontend

User: Artem M. Karavaev

A216588 Number of Hamiltonian cycles in C_4 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A194952 Number of Hamiltonian cycles in C_3 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

PARI

Python

Formula

Extensions

A181584 Number of cycles of length (2n+1)^2-1 on 2n+1 X 2n+1 square grid.

Views

Author

Keywords

Comments

Links

Crossrefs

A180582 Number of Hamiltonian cycles in C_6 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A180583 Number of Hamiltonian cycles in C_7 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A180585 Number of Hamiltonian cycles in C_9 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A180586 Number of Hamiltonian cycles in C_10 X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A180587 Number of Hamiltonian cycles in C_11 X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A180588 Number of Hamiltonian cycles in C_12 X P_n.

Views

Author

Keywords

Comments