A114582 Number of Motzkin paths of length n having no UDH's starting at level 0 (U=(1,1), H=(1,0), D=(1,-1)).

1, 1, 2, 3, 7, 16, 40, 100, 256, 663, 1741, 4620, 12376, 33416, 90853, 248515, 683429, 1888449, 5240509, 14598709, 40810390, 114447429, 321885675, 907723460, 2566079622, 7270598910, 20643413513, 58727234739, 167373377361

Offset

0,3

Comments

Column 0 of A114581.

Links

Table of n, a(n) for n=0..28.

Formula

G.f.: 2/(1 - z + 2z^3 + sqrt(1-2z-3z^2)).

a(n) = Sum(k=1..n/3+1, (k*Sum(j=0..n-2*k+3, binomial(j,k+2*j-n-3)*binomial(n-2*k+3,j)))/(n-2*k+3)*(-1)^(k-1)). - Vladimir Kruchinin, Oct 22 2011

D-finite with recurrence +(n+1)*a(n) +2*(-n+1)*a(n-1) +2*(-2*n+1)*a(n-2) +(3*n-1)*a(n-3) +(n-1)*a(n-4) +3*(-n+1)*a(n-5)=0. - R. J. Mathar, Mar 24 2018

Example

a(3)=3 because we have HHH, HUD, UHD, where U=(1,1), H=(1,0), D=(1,-1).

Maple

G:=2/(1-z+2*z^3+sqrt(1-2*z-3*z^2)): Gser:=series(G, z=0, 35): 1, seq(coeff(Gser, z^n), n=1..32);

Prog

(Maxima)
a(n):=sum((k*sum(binomial(j, k+2*j-n-3)*binomial(n-2*k+3, j), j, 0, n-2*k+3))/(n-2*k+3)*(-1)^(k-1), k, 1, n/3+1); /* Vladimir Kruchinin, Oct 22 2011 */

Crossrefs

Cf. A114581.

Sequence in context: A353580 A334398 A027118 * A352816 A107387 A091487

Adjacent sequences: A114579 A114580 A114581 * A114583 A114584 A114585

Keyword

nonn

Author

Emeric Deutsch, Dec 09 2005

Status

approved