A003682 Number of (undirected) Hamiltonian paths in the n-ladder graph K_2 X P_n.

1, 4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158, 184, 212, 242, 274, 308, 344, 382, 422, 464, 508, 554, 602, 652, 704, 758, 814, 872, 932, 994, 1058, 1124, 1192, 1262, 1334, 1408, 1484, 1562, 1642, 1724, 1808, 1894, 1982, 2072, 2164

Offset

1,2

Comments

Equals row sums of triangle A144336. - Gary W. Adamson, Sep 18 2008

References

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Links

Andrew Howroyd, 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

Eric Weisstein's World of Mathematics, Hamiltonian Path

Eric Weisstein's World of Mathematics, Ladder Graph

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Formula

For n>1, a(n) = n^2 - n + 2 = A014206(n-1).

Equals binomial transform of [1, 3, 1, 1, -1, 1, -1, 1, ...]. - Gary W. Adamson, Apr 23 2008

G.f.: x(1 + x - x^2 + x^3)/(1-x)^3. - R. J. Mathar, Dec 16 2008

a(n) = floor((n^3 + 2*n)/(n+1)). - Gary Detlefs, Feb 20 2010

Except for the first term, a(n) = 2*n + a(n-1), (with a(1)=4). - Vincenzo Librandi, Dec 06 2010

a(0)=1, a(1)=4, a(2)=8, a(3)=14, a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - Harvey P. Dale, Jun 14 2011

Maple

a:=n->sum(binomial(2, 2*j)+n, j=0..n): seq(a(n), n=0..46); # Zerinvary Lajos, Feb 22 2007
seq(floor((n^3+2*n)/(n+1)), n=1..47); # Gary Detlefs, Feb 20 2010

Mathematica

Join[{1}, Table[n^2 - n + 2, {n, 2, 50}]] (* Harvey P. Dale, Jun 14 2011 *)
Join[{1}, LinearRecurrence[{3, -3, 1}, {4, 8, 14}, 50]] (* Harvey P. Dale, Jun 14 2011 *)

Prog

(PARI) a(n)=if(n>1, n^2-n+2, 1) \\ Charles R Greathouse IV, Jan 05 2018

Crossrefs

Row n=2 of A332307.

Equals A002061(n) + 1, n > 1.

Cf. A144336. - Gary W. Adamson, Sep 18 2008

Sequence in context: A054347 A194149 A351362 * A333700 A011897 A110895

Adjacent sequences: A003679 A003680 A003681 * A003683 A003684 A003685

Keyword

nonn,easy

Author

Frans J. Faase

Status

approved