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,4

Comments

Hankel transform of this sequence forms A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

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.

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

Example

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.

Mathematica

CoefficientList[ Series[(1 + 3x - Sqrt[1 - 6x + 5x^2])/(2x^2 + 6x), {x, 0, 25}], x] (* Robert G. Wilson v *)

Prog

(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
(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
(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

Crossrefs

Cf. A000957, A001006, A002212, A005043, A097331, A000108.

Sequence in context: A270561 A259858 A359711 * A200030 A084782 A149068

Adjacent sequences: A117638 A117639 A117640 * A117642 A117643 A117644

Keyword

easy,nonn

Author

Louis Shapiro, Apr 10 2006

Status

approved