A003742 Number of 2-factors in O_5 X P_n.

6, 327, 11040, 406731, 14683587, 532938234, 19313709882, 700238873703, 25384576377228, 920260033555854, 33361543878231264, 1209436952734137963, 43844979765366718719, 1589485790652572990865, 57622670964678806649843, 2088960040762846005003294

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..650

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 (26,396,-707,-6539,7239,-405).

Formula

a(1) = 6,

a(2) = 327,

a(3) = 11040,

a(4) = 406731,

a(5) = 14683587,

a(6) = 532938234, and

a(n) = 26a(n-1) + 396a(n-2) - 707a(n-3) - 6539a(n-4) + 7239a(n-5) - 405a(n-6).

G.f.: -3*x*(135*x^5 -2388*x^4 +1853*x^3 -54*x^2 -57*x -2)/(405*x^6 -7239*x^5 +6539*x^4 +707*x^3 -396*x^2 -26*x +1). - Colin Barker, Aug 30 2012

Mathematica

CoefficientList[Series[-3 (135 x^5 - 2388 x^4 + 1853 x^3 - 54 x^2 - 57 x - 2)/(405 x^6 - 7239 x^5 + 6539 x^4 + 707 x^3 - 396 x^2 - 26 x + 1), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 14 2013 *)
LinearRecurrence[{26, 396, -707, -6539, 7239, -405}, {6, 327, 11040, 406731, 14683587, 532938234}, 20] (* Harvey P. Dale, Dec 14 2015 *)

Prog

(Magma) I:=[6, 327, 11040, 406731, 14683587, 532938234]; [n le 6 select I[n] else 26*Self(n-1)+396*Self(n-2)-707*Self(n-3)-6539*Self(n-4)+7239*Self(n-5)-405*Self(n-6): n in [1..20]]; // Vincenzo Librandi, Oct 14 2013
(PARI) Vec(-3*x*(135*x^5-2388*x^4+1853*x^3-54*x^2-57*x-2)/(405*x^6-7239*x^5+6539*x^4+707*x^3-396*x^2-26*x+1)+O(x^99)) \\ Charles R Greathouse IV, Jun 23 2020

Crossrefs

Sequence in context: A135397 A042421 A221884 * A324099 A135195 A273031

Adjacent sequences: A003739 A003740 A003741 * A003743 A003744 A003745

Keyword

nonn,easy

Author

Frans J. Faase

Extensions

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

Status

approved