A137882 Number of (directed) Hamiltonian paths in the n-ladder graph.

2, 8, 16, 28, 44, 64, 88, 116, 148, 184, 224, 268, 316, 368, 424, 484, 548, 616, 688, 764, 844, 928, 1016, 1108, 1204, 1304, 1408, 1516, 1628, 1744, 1864, 1988, 2116, 2248, 2384, 2524, 2668, 2816, 2968, 3124, 3284, 3448, 3616, 3788, 3964, 4144, 4328, 4516, 4708, 4904, 5104, 5308, 5516, 5728, 5944, 6164, 6388, 6616, 6848, 7084, 7324, 7568, 7816

Offset: 1

Author

Eric W. Weisstein, Feb 20 2008

Keywords

• nonn
• easy

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• 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

Cf. A001221, A001222, A003682, A154685.

Programs

Maple

A137882:=n->2*(n^2-n+2): 2,seq(A137882(n), n=2..100); # Wesley Ivan Hurt, Apr 25 2017

Mathematica

CoefficientList[Series[2*x*(1 + x - x^2 + x^3)/(1 - x)^3, {x,0,50}], x] (* G. C. Greubel, Apr 25 2017 *)
LinearRecurrence[{3,-3,1},{2,8,16,28},70] (* Harvey P. Dale, Nov 15 2018 *)

PARI

my(x='x+O('x^50)); Vec(2*x*(1 + x - x^2 + x^3)/(1 - x)^3) \\ G. C. Greubel, Apr 25 2017

Formula

For n>2, m = p^3*q (p,q = primes), a(n) = Sum_{d|m} (n-1)^(bigomega(d) - omega(d)) = Sum_{d|m} (n-1)^(A001222(d) - A001221(d)). - Jaroslav Krizek, Sep 24 2009

For n>1, a(n) = 2*(n^2 - n + 2); first diagonal of A154685. - Vincenzo Librandi, Nov 24 2010

G.f.: 2*x*(1+x-x^2+x^3)/(1-x)^3. - Colin Barker, Jan 20 2012

Sum_{n>=1} 1/a(n) = 1/4 + Pi*tanh(sqrt(7)*Pi/2)/(2*sqrt(7)). - Amiram Eldar, Dec 23 2022

From Elmo R. Oliveira, Jun 06 2025: (Start)

E.g.f.: 2*(exp(x)*(2 + x^2) - (2 + x)).

a(n) = 2*A003682(n).

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 4. (End)

Extensions

Extended and formula corrected by Max Alekseyev, Apr 11 2009

Corrected the formula which was confusing offsets - R. J. Mathar, Jun 04 2010