|
%I #26 Sep 15 2020 05:55:24
%S 1,1,2,3,6,11,23,48,107,244,578,1402,3485,8826,22729,59340,156766,
%T 418319,1125956,3053400,8334578,22881070,63135802,175000959,487042069,
%U 1360440914,3812681435,10717405374,30209571942,85368323429,241801775480,686366436772
%N Number of Motzkin paths of length n with no level steps at height 1.
%H Alois P. Heinz, <a href="/A217312/b217312.txt">Table of n, a(n) for n = 0..1000</a>
%F 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).
%F 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
%F 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
%F a(n) ~ 3^(n - 1/2) / (2*sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jul 20 2019
%e The a(4) = 6 paths are HHHH, UDUD, HUDH, UDHH, HHUD, UUDD.
%p b:= proc(n,y) option remember;
%p `if`(y>n, 0, `if`(n=0, 1, `if`(y<>1, b(n-1, y), 0)+
%p `if`(y>0, b(n-1, y-1), 0)+ b(n-1, y+1)))
%p end:
%p a:= n-> b(n, 0):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Mar 18 2013
%t 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_ *)
%o (Maxima)
%o 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 */
%Y Cf. A001006, A005043.
%K nonn
%O 0,3
%A _José Luis Ramírez Ramírez_, Mar 17 2013
|
