login
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

%I #12 Jul 24 2022 11:00:15

%S 1,1,2,3,7,16,40,100,256,663,1741,4620,12376,33416,90853,248515,

%T 683429,1888449,5240509,14598709,40810390,114447429,321885675,

%U 907723460,2566079622,7270598910,20643413513,58727234739,167373377361

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

%C Column 0 of A114581.

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

%F 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

%F 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

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

%p 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);

%o (Maxima)

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

%Y Cf. A114581.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Dec 09 2005