A359855 -id:A359855 - cp's OEIS frontend

A003699 Number of Hamiltonian cycles in C_4 X P_n.

1, 6, 22, 82, 306, 1142, 4262, 15906, 59362, 221542, 826806, 3085682, 11515922, 42978006, 160396102, 598606402, 2234029506, 8337511622, 31116016982, 116126556306, 433390208242, 1617434276662, 6036346898406, 22527953316962, 84075466369442, 313773912160806

Offset: 1

Frans J. Faase

a(n) is the number of generalized compositions of n when there are i^2+i-1 different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010

Is this the same as the sequence visible in Table 5 of Pettersson, 2014? - N. J. A. Sloane, Jun 05 2015

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Column k=4 of A359855.
First differences of A052530 and A071954.
Cf. A001353, A001835.

a:=[6,22];; for n in [3..20] do a[n]:=4a[n-1]-a[n-2]; od; Concatenation([1], a); # G. C. Greubel, Dec 23 2019

I:=[1,6,22]; [n le 3 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 13 2018

seq( simplify( `if`(n=1, 1, 2*(ChebyshevU(n-1,2) - ChebyshevU(n-2,2))) ), n=1..30); # G. C. Greubel, Dec 23 2019

Join[{1},LinearRecurrence[{4,-1},{6,22},30]] (* Harvey P. Dale, Jul 19 2011 *)
Table[If[n<2, n, 2*(ChebyshevU[n-1, 2] - ChebyshevU[n-2, 2])], {n,30}] (* G. C. Greubel, Dec 23 2019 *)

(a[1] : 1, a[2] : 6, a[3] : 22, a[n] := 4*a[n - 1] - a[n - 2], makelist(a[n], n, 1, 50)); /* Franck Maminirina Ramaharo, Nov 12 2018 */

vector(30, n, if(n==1, 1, 2*(polchebyshev(n-1, 2, 2) - polchebyshev(n-2, 2, 2))) ) \\ G. C. Greubel, Dec 23 2019

[1]+[2*(chebyshev_U(n-1,2) - chebyshev_U(n-2,2)) for n in (2..30)] # G. C. Greubel, Dec 23 2019

a(n) = 2 * A001835(n), n > 1.
From Benoit Cloitre, Mar 28 2003: (Start)
a(n) = ceiling((1 - sqrt(1/3))*(2 + sqrt(3))^n) for n > 1.
a(1) = 1, a(2) = 6, a(3) = 22 and for n > 3, a(n) = 4*a(n-1) - a(n-2). (End)
O.g.f.: x*(1 + 2*x - x^2)/(1-4*x+x^2) = -2 - x + 2*(1 - 3*x)/(1-4*x+x^2). - R. J. Mathar, Nov 23 2007
From Franck Maminirina Ramaharo, Nov 12 2018: (Start)
a(n) = ((1 + sqrt(3))*(2 - sqrt(3))^n - (1 - sqrt(3))*(2 + sqrt(3))^n)/sqrt(3), n > 1.
E.g.f.: ((1 + sqrt(3))*exp((2 - sqrt(3))*x) - (1 - sqrt(3))*exp((2 + sqrt(3))*x) - (2 + x)*sqrt(3))/sqrt(3). (End)
a(n) = 2*(ChebyshevU(n-1, 2) - ChebyshevU(n-2, 2)) for n >1, with a(1)=1. - G. C. Greubel, Dec 23 2019

A003731 Number of Hamiltonian cycles in C_5 X P_n.

Original entry on oeis.org

1, 5, 30, 160, 850, 4520, 24040, 127860, 680040, 3616880, 19236840, 102313600, 544168000, 2894227280, 15393318880, 81871340160, 435443220000, 2315960597120, 12317733383040, 65513444349760, 348441653760640, 1853231611930880, 9856649945242240, 52423856531251200

Offset: 1

Frans J. Faase

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Index entries for linear recurrences with constant coefficients, signature (6,-4,2).

Column k=5 of A359855.

I:=[1,5,30,160]; [n le 4 select I[n] else 6*Self(n-1)-4*Self(n-2)+2*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Oct 14 2013

CoefficientList[Series[(1 - x + 4 x^2 - 2 x^3)/(1 - 6 x + 4 x^2 - 2 x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 14 2013 *)

a(n)=([0,1,0; 0,0,1; 2,-4,6]^(n-1)*[1;5;30])[1,1] \\ Charles R Greathouse IV, Jun 23 2020

a(n) = 6*a(n-1) - 4*a(n-2) + 2*a(n-3) for n > 4.

G.f.: x*(1 - x + 4*x^2 - 2*x^3)/(1 - 6*x + 4*x^2 - 2*x^3). - Colin Barker, Sep 01 2012

More terms from Vincenzo Librandi, Oct 14 2013

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

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

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

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

cp's OEIS Frontend

A003699 Number of Hamiltonian cycles in C_4 X P_n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

Sage

Formula

A003731 Number of Hamiltonian cycles in C_5 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A180582 Number of Hamiltonian cycles in C_6 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A180584 Number of Hamiltonian cycles in C_8 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

A180583 Number of Hamiltonian cycles in C_7 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula