A117641 Number of 3-Motzkin paths of length n with no level steps at height 0.
1, 0, 1, 3, 11, 42, 167, 684, 2867, 12240, 53043, 232731, 1031829, 4615542, 20805081, 94410363, 430945739, 1977366192, 9115261211, 42195093993, 196060049129, 914110333422, 4275222950221, 20051858039718, 94294269673861
Offset: 0
Examples
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.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
- L. W. Shapiro, C. J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.
Programs
-
Magma
R
:=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 -
Mathematica
CoefficientList[ Series[(1 + 3x - Sqrt[1 - 6x + 5x^2])/(2x^2 + 6x), {x, 0, 25}], x] (* Robert G. Wilson v *) -
Maxima
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 */
-
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 -
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
Formula
G.f.: (1 +3*x -sqrt(1 -6*x +5*x^2))/(2*x*(3+x)).
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
a(n) = A126970(n,0). - Philippe Deléham, Nov 24 2009
a(n) = Sum_{k=0..n} A091965(n,k)*(-3)^k. - Philippe Deléham, Nov 28 2009
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
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
a(n) ~ 5^(n+3/2) / (32 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014
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
Comments