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,2

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

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

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

Crossrefs

Row n=4 of A332307.

Sequence in context: A371420 A307253 A125849 * A022674 A044152 A044533

Adjacent sequences: A003692 A003693 A003694 * A003696 A003697 A003698

Keyword

nonn,easy

Author

Frans J. Faase

Extensions

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

Status

approved