%I #37 Feb 10 2020 12:57:13
%S 1,14,62,276,1006,3610,12010,38984,122188,375122,1128446,3342794,
%T 9767588,28217820,80709424,228864620,644060262,1800346140,5002457832,
%U 13825549136,38026348240,104133664506,284037629690,771953153918,2091075938320,5647162827592,15208169217918
%N Number of Hamiltonian paths in P_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="/A003695/b003695.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. Kloczkowski, and R. L. Jernigan, <a href="https://doi.org/10.1063/1.477128">Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices</a>, The Journal of Chemical Physics 109, 5134 (1998); doi: 10.1063/1.477128.
%H <a href="/index/Rec#order_14">Index entries for linear recurrences with constant coefficients</a>, signature (6,-5,-27,37,48,-69,-38,57,-2,-31,13,3,-4,1).
%F a(1) = 1,
%F a(2) = 14,
%F a(3) = 62,
%F a(4) = 276,
%F a(5) = 1006,
%F a(6) = 3610,
%F a(7) = 12010,
%F a(8) = 38984,
%F a(9) = 122188,
%F a(10) = 375122,
%F a(11) = 1128446,
%F a(12) = 3342794,
%F a(13) = 9767588,
%F a(14) = 28217820,
%F a(15) = 80709424,
%F a(16) = 228864620 and
%F a(n) = 6a(n-1) - 5a(n-2) - 27a(n-3) + 37a(n-4) + 48a(n-5) - 69a(n-6) - 38a(n-7) + 57a(n-8) - 2a(n-9) - 31a(n-10) + 13a(n-11) + 3a(n-12) - 4a(n-13) + a(n-14).
%F G.f.: x +2*x^2*(x^14 -3*x^13 +4*x^12 +10*x^11 -30*x^10 +16*x^9 +36*x^8 -72*x^7 +43*x^6 +67*x^5 -55*x^4 -19*x^3 +13*x^2 +11*x -7)/((x^2 +x -1) *(x^4 -2*x^3 +2*x^2 +2*x -1)^2 *(x^4 -x^3 -3*x^2 -x +1)). - _Colin Barker_, Aug 23 2012
%t CoefficientList[Series[1 + 2 x (x^14 - 3 x^13 + 4 x^12 + 10 x^11 - 30 x^10 + 16 x^9 + 36 x^8 - 72 x^7 + 43 x^6 + 67 x^5 - 55 x^4 - 19 x^3 + 13 x^2 + 11 x - 7)/((x^2 + x - 1) (x^4 - 2 x^3 + 2 x^2 + 2 x - 1)^2 (x^4 - x^3 - 3 x^2 - x + 1)), {x, 0, 40}], x] (* _Vincenzo Librandi_, Oct 13 2013 *)
%Y Row n=4 of A332307.
%K nonn,easy
%O 1,2
%A _Frans J. Faase_
%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009