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

Author

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

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A001006, A005043.

Programs

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

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

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