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!)
A253918 Number of Motzkin n-paths with two kinds of level steps both of which are final steps. 1
1, 2, 1, 4, 6, 12, 29, 56, 134, 300, 682, 1624, 3772, 9016, 21597, 51888, 126086, 306636, 750398, 1843864, 4543604, 11242088, 27887730, 69378192, 173050396, 432596216, 1083862132, 2720961520, 6843557944, 17242789104, 43514507997, 109983815264, 278385212358 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of words of length n on alphabet {U,D,L,R} where U is upstep, D is downstep, L and R are level steps and can only be immediately followed by D or end of word. Defining equation is A = 1 + L + R + UADA.

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

FORMULA

When convolved with itself yields sequence shifted left two places.

G.f. A(x) satisfies A(x) = 1 + 2*x + (A(x)*x)^2.

G.f.: (1 - sqrt(1 - 4*x^2 - 8*x^3)) / (2*x^2).

0 = a(n)*(8*n+4) + a(n+1)*(4*n+8) + a(n+3)*(-n-5) for n>=-1.

a(n) = Sum_{k=0..n}((binomial(k+1,n-2*k)*binomial(2*k,k)*2^(n-2*k))/(k+1)). - Vladimir Kruchinin, Mar 11 2016

a(n) ~ sqrt(3-4*c^2) * 4^n * c^n * (1+2*c)^(n+1) / (sqrt(Pi)*n^(3/2)), where c = 0.37743883312334638... is the root of the equation 4*c^2*(1 + 2*c) = 1. - Vaclav Kotesovec, Mar 10 2016

EXAMPLE

G.f. = 1 + 2*x + x^2 + 4*x^3 + 6*x^4 + 12*x^5 + 29*x^6 + 56*x^7 + ...

A = 1 + (L + R) + (UD) + (ULD + URD + UDR + UDL) + (UDUD + UUDD + ULDL + ULDR + URDL + URDR) + ...

MATHEMATICA

a[ n_] := SeriesCoefficient[ (1 - Sqrt[1 - 4 x^2 - 8x^3]) / (2 x^2), {x, 0, n}];

PROG

(PARI) {a(n) = if( n<0, 0, polcoeff( (1 - sqrt(1 - 4*x^2 - 8*x^3  + x^3*O(x^n))) / (2*x^2), n))};

(PARI) {a(n) = my(A); if( n<0, 0, A = O(x); for(k=0, n\2, A = 1 + 2*x + sqr(x*A)); polcoeff( A, n))};

(Maxima)

a(n):=sum((binomial(k+1, n-2*k)*binomial(2*k, k)*2^(n-2*k))/(k+1), k, 0, n); /* Vladimir Kruchinin, Mar 11 2016 */

CROSSREFS

Cf. A143013.

Sequence in context: A034424 A095012 A192781 * A269415 A019142 A330536

Adjacent sequences:  A253915 A253916 A253917 * A253919 A253920 A253921

KEYWORD

nonn

AUTHOR

Michael Somos, Jan 19 2015

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 August 14 13:46 EDT 2020. Contains 336481 sequences. (Running on oeis4.)