login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117641 Number of 3-Motzkin paths of length n with no level steps at height 0. 13
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 (list; graph; refs; listen; history; text; internal format)
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: A143464 A270561 A259858 * A200030 A084782 A149068

Adjacent sequences:  A117638 A117639 A117640 * A117642 A117643 A117644

KEYWORD

easy,nonn

AUTHOR

Louis Shapiro, Apr 10 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 00:14 EDT 2021. Contains 345403 sequences. (Running on oeis4.)