A217312 Number of Motzkin paths of length n with no level steps at height 1.

1, 1, 2, 3, 6, 11, 23, 48, 107, 244, 578, 1402, 3485, 8826, 22729, 59340, 156766, 418319, 1125956, 3053400, 8334578, 22881070, 63135802, 175000959, 487042069, 1360440914, 3812681435, 10717405374, 30209571942, 85368323429, 241801775480, 686366436772

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

G.f.: 2*(1+x)/(2-x-3*x^2+x*sqrt(1-2*x-3*x^2)) = 1/(1-x-x^2*R), where R is the g.f. of Riordan numbers (A005043).

a(n) = 1+Sum_{k=0..(n-1)/2}((k+1)*Sum_{i=0..n-2*k-1}(((Sum_{j=0..i}((-1)^(j-i)*binomial(k+i+1,i-j)*binomial(k+2*j,j)))*binomial(n-k-i-1,k+1))/(k+i+1))). - Vladimir Kruchinin, Mar 12 2016

D-finite with recurrence (-n+1)*a(n) +(4*n-7)*a(n-1) -3*a(n-2) +(-11*n+32)*a(n-3) +3*(n-1)*a(n-4) +9*(n-4)*a(n-5)=0. - R. J. Mathar, Sep 24 2016

a(n) ~ 3^(n - 1/2) / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 20 2019

Example

The a(4) = 6 paths are HHHH, UDUD, HUDH, UDHH, HHUD, UUDD.

Maple

b:= proc(n, y) option remember;
       `if`(y>n, 0, `if`(n=0, 1, `if`(y<>1, b(n-1, y), 0)+
       `if`(y>0, b(n-1, y-1), 0)+ b(n-1, y+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 18 2013

Mathematica

b[n_, y_] := b[n, y] = If[y>n, 0, If[n == 0, 1, If[y != 1, b[n-1, y], 0] + If[y>0, b[n-1, y-1], 0] + b[n-1, y+1]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jan 22 2017, after Alois P. Heinz *)

Prog

(Maxima)
a(n):=(sum((k+1)*sum(((sum((-1)^(j-i)*binomial(k+i+1, i-j)*binomial(k+2*j, j), j, 0, i))*binomial(n-k-i-1, k+1))/(k+i+1), i, 0, n-2*k-1), k, 0, (n-1)/2))+1; /* Vladimir Kruchinin, Mar 12 2016 */

Crossrefs

Cf. A001006, A005043.

Sequence in context: A277796 A123465 A000055 * A006787 A176425 A000992

Adjacent sequences: A217309 A217310 A217311 * A217313 A217314 A217315

Keyword

nonn

Author

José Luis Ramírez Ramírez, Mar 17 2013

Status

approved