A003695 Number of Hamiltonian paths in P_4 X P_n.
1, 14, 62, 276, 1006, 3610, 12010, 38984, 122188, 375122, 1128446, 3342794, 9767588, 28217820, 80709424, 228864620, 644060262, 1800346140, 5002457832, 13825549136, 38026348240, 104133664506, 284037629690, 771953153918, 2091075938320, 5647162827592, 15208169217918
Offset: 1
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
- A. Kloczkowski, and R. L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices, The Journal of Chemical Physics 109, 5134 (1998); doi: 10.1063/1.477128.
- Index entries for linear recurrences with constant coefficients, signature (6,-5,-27,37,48,-69,-38,57,-2,-31,13,3,-4,1).
Crossrefs
Row n=4 of A332307.
Programs
-
Mathematica
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 *)
Formula
a(1) = 1,
a(2) = 14,
a(3) = 62,
a(4) = 276,
a(5) = 1006,
a(6) = 3610,
a(7) = 12010,
a(8) = 38984,
a(9) = 122188,
a(10) = 375122,
a(11) = 1128446,
a(12) = 3342794,
a(13) = 9767588,
a(14) = 28217820,
a(15) = 80709424,
a(16) = 228864620 and
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).
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
Extensions
Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009