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, 2258, 2354, 2452, 2552, 2654
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
- 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).
Crossrefs
Row n=2 of A332307.
Equals A002061(n) + 1, n > 1.
Cf. A144336. - Gary W. Adamson, Sep 18 2008
Cf. A137882.
Programs
-
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 *) -
PARI
a(n)=if(n>1, n^2-n+2, 1) \\ Charles R Greathouse IV, Jan 05 2018
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(n) = 3*a(n-1) - 3*a(n-2) + a(n-3), a(1)=1, a(2)=4, a(3)=8. - Harvey P. Dale, Jun 14 2011
Sum_{n>=1} 1/a(n) = 1/2 + Pi*tanh(Pi*sqrt(7)/2)/sqrt(7) = 1.686827... - R. J. Mathar, Apr 24 2024
From Elmo R. Oliveira, Jun 06 2025: (Start)
E.g.f.: exp(x)*(2 + x^2) - (2 + x).
a(n) = A137882(n)/2. (End)
Comments