%I #28 Sep 08 2022 08:44:32
%S 1,9,53,341,2169,13825,88093,561357,3577121,22794425,145252485,
%T 925589701,5898117961,37584466929,239498796653,1526153708861,
%U 9725080775409,61970950592425,394896331045333,2516390514947637
%N Number of 2-factors in C_4 X P_n.
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H Vincenzo Librandi, <a href="/A003698/b003698.txt">Table of n, a(n) for n = 1..1000</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,3,-4).
%F a(n) = 6*a(n-1) + 3*a(n-2) - 4*a(n-3), n>3.
%F G.f.: x*(1-x)*(1+4*x)/((1+x)*(1-7*x+4*x^2)). - _Colin Barker_, Aug 30 2012
%p 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
%t 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 *)
%t 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 *)
%o (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
%o (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
%o (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
%o (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
%Y Cf. A190973.
%K nonn,easy
%O 1,2
%A _Frans J. Faase_