A003698 Number of 2-factors in C_4 X P_n.

1, 9, 53, 341, 2169, 13825, 88093, 561357, 3577121, 22794425, 145252485, 925589701, 5898117961, 37584466929, 239498796653, 1526153708861, 9725080775409, 61970950592425, 394896331045333, 2516390514947637

Offset

1,2

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..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,3,-4).

Formula

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

G.f.: x*(1-x)*(1+4*x)/((1+x)*(1-7*x+4*x^2)). - Colin Barker, Aug 30 2012

Maple

seq( simplify( (-1)^n + 2^n*Chebyshev(n, 7/4) - 2^(n+1)*ChebyshevU(n-1, 7/4))/2 ), n=1..30); # G. C. Greubel, Dec 24 2019

Mathematica

Rest@CoefficientList[Series[x*(1-x)*(1+4*x)/((1+x)*(1-7*x+4*x^2)), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 13 2013 *)
Table[((-1)^n + 2^n*ChebyshevU[n, 7/4] - 2^(n+1)*ChebyshevU[n-1, 7/4])/2, {n, 30}] (* G. C. Greubel, Dec 24 2019 *)

Prog

(PARI) vector(30, n, ((-1)^n + 2^n*polchebyshev(n, 2, 7/4) - 2^(n+1)*polchebyshev(n-1, 2, 7/4))/2 ) \\ G. C. Greubel, Dec 24 2019
(Magma) I:=[1, 9, 53]; [n le 3 select I[n] else 6*Self(n-1) +3*Self(n-2) -4*Self(n-3): n in [1..20]]; // G. C. Greubel, Dec 24 2019
(Sage) [((-1)^n + 2^n*chebyshev_U(n, 7/4) - 2^(n+1)*chebyshev_U(n-1, 7/4))/2 for n in (1..30)] # G. C. Greubel, Dec 24 2019
(GAP) a:=[1, 9, 53];; for n in [4..30] do a[n]:=6*a[n-1]+3*a[n-2]-4*a[n-3]; od; a; # G. C. Greubel, Dec 24 2019

Crossrefs

Cf. A190973.

Sequence in context: A295203 A334977 A038761 * A001688 A144040 A336184

Adjacent sequences: A003695 A003696 A003697 * A003699 A003700 A003701

Keyword

nonn,easy

Author

Frans J. Faase

Status

approved