A253918 Number of Motzkin n-paths with two kinds of level steps both of which are final steps.

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

Offset: 0

Author

Michael Somos, Jan 19 2015

Keywords

• nonn

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.

Examples

			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) + ...
		

Links

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

Crossrefs

Cf. A143013.

Programs

Mathematica

a[ n_] := SeriesCoefficient[ (1 - Sqrt[1 - 4 x^2 - 8x^3]) / (2 x^2), {x, 0, 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 */

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))};

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