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
Keywords
Examples
a(3)=3 because we have HHH, HUD, UHD, where U=(1,1), H=(1,0), D=(1,-1).
Crossrefs
Cf. A114581.
Programs
-
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);
-
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 */
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
Comments