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
KEYWORD
nonn
AUTHOR
Michael Somos, Jan 19 2015
STATUS
approved