A003737 Number of Hamiltonian cycles in W_5 X P_n.

4, 92, 1432, 22632, 357952, 5660752, 89521984, 1415743552, 22389250144, 354074376800, 5599502597088, 88553228914208, 1400423379497056, 22146969296658080, 350242830993566816, 5538908688560111008, 87594967677616439904, 1385268975148564102048, 21907310252932371420768

Offset

1,1

References

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..850

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 (13,50,-80,-120,188,32,-16).

Formula

a(1) = 4,

a(2) = 92,

a(3) = 1432,

a(4) = 22632,

a(5) = 357952,

a(6) = 5660752,

a(7) = 89521984,

a(8) = 1415743552, and

a(n) = 13a(n-1) + 50a(n-2) - 80a(n-3) - 120a(n-4) + 188a(n-5) + 32a(n-6) - 16a(n-7).

G.f.: 4*x*(2*x^2 -3*x -1)*(8*x^5 -40*x^4 +22*x^3 +10*x^2 -7*x -1)/(16*x^7 -32*x^6 -188*x^5 +120*x^4 +80*x^3 -50*x^2 -13*x +1). - Colin Barker, Aug 31 2012

Mathematica

CoefficientList[Series[4 (2 x^2 - 3 x - 1) (8 x^5 - 40 x^4 + 22 x^3 + 10 x^2 - 7 x - 1)/(16 x^7 - 32 x^6 - 188 x^5 + 120 x^4 + 80 x^3 - 50 x^2 - 13 x + 1), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 14 2013 *)

Prog

(Magma) I:=[4, 92, 1432, 22632, 357952, 5660752, 89521984, 1415743552]; [n le 8 select I[n] else 13*Self(n-1)+50*Self(n-2)-80*Self(n-3)-120*Self(n-4)+188*Self(n-5)+32*Self(n-6)-16*Self(n-7): n in [1..20]]; // Vincenzo Librandi, Oct 14 2013

Crossrefs

Sequence in context: A248041 A209984 A113252 * A362511 A265238 A322769

Adjacent sequences: A003734 A003735 A003736 * A003738 A003739 A003740

Keyword

nonn,easy

Author

Frans J. Faase

Extensions

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

Status

approved