OFFSET
0,5
COMMENTS
Diagonal sums of number triangle A117434.
a(n) = number of Motzkin n-paths (A001006) in which every flatstep (F) is followed by a downstep (D). For example, a(5)=4 counts UDUFD, UFDUD, UUDFD, UUFDD. - David Callan, Jun 07 2006
a(n) = number of lattice paths in the first quadrant from (0,0) to (n,0) using only steps U1=(1,1), U2=(2,1) and D=(1,-1). E.g. a(6)=7 because we have U1DU1DU1D, U1U1U1DDD, U1U1DU1DD, U1DU1U1DD, U1U1DDU1D, U2DU2D and U2U2DD. - José Luis Ramírez Ramírez, May 27 2013
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
FORMULA
a(n) = Sum_{k=0..floor(n/2)} C(k)*C(k,n-2k).
D-finite with recurrence (n+2)*a(n) +(n+2)*a(n-1) +4*(1-n)*a(n-2) +2*(7-4*n)*a(n-3) +2*(5-2*n)*a(n-4)=0. - R. J. Mathar, Nov 15 2011
G.f. A(x) satisfies A(x) = 1 / (1 - x^2 / (1 - x / (1 - x^2 * A(x)))). - Michael Somos, May 12 2012
G.f.: (1-sqrt(1-4*z^2*(1+z)))/(2*z^2*(1+z)). - José Luis Ramírez Ramírez, May 27 2013
a(n) ~ sqrt(3 - 1/9*(-2 + (19-3*sqrt(33))^(1/3) + (19+3*sqrt(33))^(1/3))^2) * (((-2 + (19-3*sqrt(33))^(1/3) + (19+3*sqrt(33))^(1/3)) * (4 + (19-3*sqrt(33))^(1/3) + (19+3*sqrt(33))^(1/3)))/9)^n /(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Sep 16 2013
EXAMPLE
1 + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 15*x^7 + 29*x^8 + 61*x^9 + ...
MATHEMATICA
Table[Sum[Binomial[k, n - 2*k]*CatalanNumber[k], {k, 0, Floor[n/2]}], {n, 0, 50}] (* G. C. Greubel, Feb 03 2017 *)
PROG
(PARI) {a(n) = local(A); A = O(x^0); for( k=0, n\5, A = 1 / (1 - x^2 / (1 - x / (1 - x^2 * A)))); polcoeff( A, n)} /* Michael Somos, May 12 2012 */
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Mar 14 2006
STATUS
approved