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

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

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

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

Prog

(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

Crossrefs

Cf. A001221, A001222, A154685.

Sequence in context: A322945 A157512 A252594 * A194643 A327329 A136514

Adjacent sequences: A137879 A137880 A137881 * A137883 A137884 A137885

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 20 2008

Extensions

Extended and formula corrected by Max Alekseyev, Apr 11 2009

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

Status

approved