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

Author

Frans J. Faase

Keywords

• nonn
• easy

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

Crossrefs

Cf. A190973.

Programs

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

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

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 *)

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

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

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