%I #29 Sep 08 2022 08:44:32
%S 4,72,584,4016,24656,140624,761960,3976704,20173280,100097008,
%T 488003448,2345542720,11142878992,52426883056,244682331976,
%U 1134222633280,5227498311360,23975219772016,109500177006104,498322800625728,2260840364623472,10230065398683632
%N Number of Hamiltonian paths 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="/A003752/b003752.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_07">Index entries for linear recurrences with constant coefficients</a>, signature (11,-36,16,67,-9,-10,2).
%F a(1) = 4,
%F a(2) = 72,
%F a(3) = 584,
%F a(4) = 4016,
%F a(5) = 24656,
%F a(6) = 140624,
%F a(7) = 761960,
%F a(8) = 3976704 and
%F a(n) = 11a(n-1) - 36a(n-2) + 16a(n-3) + 67a(n-4) - 9a(n-5) - 10a(n-6) + 2a(n-7).
%F G.f.: -4*x*(2*x^7 +4*x^6 -37*x^5 +21*x^4 +30*x^3 -16*x^2 +7*x +1)/((x +1)*(x^2 -4*x +1)^2*(2*x^2 +4*x -1)). - _Colin Barker_, Aug 30 2012
%t CoefficientList[Series[-4 (2 x^7 + 4 x^6 - 37 x^5 + 21 x^4 + 30 x^3 - 16 x^2 + 7 x + 1)/((x + 1) (x^2 - 4 x + 1)^2 (2 x^2 + 4 x - 1)), {x, 0, 40}], x] (* _Vincenzo Librandi_, Oct 14 2013 *)
%t LinearRecurrence[{11,-36,16,67,-9,-10,2},{4,72,584,4016,24656,140624,761960,3976704},30] (* _Harvey P. Dale_, May 04 2018 *)
%o (Magma) I:=[4,72,584,4016,24656,140624,761960,3976704]; [n le 8 select I[n] else 11*Self(n-1)-36*Self(n-2)+16*Self(n-3)+67*Self(n-4)-9*Self(n-5)-10*Self(n-6)+2*Self(n-7): n in [1..30]]; // _Vincenzo Librandi_, Oct 14 2013
%K nonn,easy
%O 1,1
%A _Frans J. Faase_
%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009