|
| |
|
|
A253918
|
|
Number of Motzkin n-paths with two kinds of level steps both of which are final steps.
|
|
2
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
