%I #44 Sep 08 2022 08:45:24
%S 1,0,1,3,11,42,167,684,2867,12240,53043,232731,1031829,4615542,
%T 20805081,94410363,430945739,1977366192,9115261211,42195093993,
%U 196060049129,914110333422,4275222950221,20051858039718,94294269673861
%N Number of 3-Motzkin paths of length n with no level steps at height 0.
%C Hankel transform of this sequence forms A000012 = [1,1,1,1,1,...]. - _Philippe Deléham_, Oct 24 2007
%H Vincenzo Librandi, <a href="/A117641/b117641.txt">Table of n, a(n) for n = 0..200</a>
%H Isaac DeJager, Madeleine Naquin, Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H L. W. Shapiro, C. J. Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html">A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height</a>, JIS 12 (2009) 09.3.2.
%F G.f.: (1 +3*x -sqrt(1 -6*x +5*x^2))/(2*x*(3+x)).
%F G.f. as continued fraction is 1/(1-0*x-x^2/(1-3*x-x^2/(1-3*x-x^2/(1-3*x-x^2/(.....))))). - _Paul Barry_, Dec 02 2008
%F a(n) = A126970(n,0). - _Philippe Deléham_, Nov 24 2009
%F a(n) = Sum_{k=0..n} A091965(n,k)*(-3)^k. - _Philippe Deléham_, Nov 28 2009
%F a(n) = Sum_{k=1..n} Sum_{j=0..floor((n-2*k)/2)} 3^(n-2*k-2*j)*(k/(k+2*j))*binomial(k+2*j,j)*binomial(n-k-1,n-2*k-2*j). - _José Luis Ramírez Ramírez_, Mar 22 2012
%F D-finite with recurrence: 3*(n+1)*a(n) +(-17*n+10)*a(n-1) +9*(n-3)*a(n-2) +5*(n-2)*a(n-3)=0. - _R. J. Mathar_, Dec 02 2012
%F a(n) ~ 5^(n+3/2) / (32 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Feb 13 2014
%F a(n) = 1/(n+1)*Sum_{j=0..floor(n/2)} 3^(n-2*j)*C(n+1,j)*C(n-j-1,n-2*j). - _Vladimir Kruchinin_, Apr 04 2019
%e The a(4) = 11 paths are UUDD, UDUD and 9 of the form UXYD where each of X and Y are level steps in any of three colors.
%t CoefficientList[ Series[(1 + 3x - Sqrt[1 - 6x + 5x^2])/(2x^2 + 6x), {x, 0, 25}], x] (* _Robert G. Wilson v_ *)
%o (Maxima)
%o a(n):=sum(3^(n-2*j)*binomial(n+1,j)*binomial(n-j-1,n-2*j),j,0,floor(n/2))/(n+1); /* _Vladimir Kruchinin_, Apr 04 2019 */
%o (PARI) my(x='x+O('x^30)); Vec( (1+3*x-sqrt(1-6*x+5*x^2))/(2*x*(3+x)) ) \\ _G. C. Greubel_, Apr 04 2019
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (1+3*x-Sqrt(1-6*x+5*x^2))/(2*x*(3+x)) )); // _G. C. Greubel_, Apr 04 2019
%o (Sage) ((1+3*x-sqrt(1-6*x+5*x^2))/(2*x*(3+x))).series(x, 30).coefficients(x, sparse=False) # _G. C. Greubel_, Apr 04 2019
%Y Cf. A000957, A001006, A002212, A005043, A097331, A000108.
%K easy,nonn
%O 0,4
%A _Louis Shapiro_, Apr 10 2006