A115178 Expansion of c(x^2+x^3), c(x) the g.f. of A000108.

1, 0, 1, 1, 2, 4, 7, 15, 29, 61, 126, 266, 566, 1212, 2619, 5685, 12419, 27247, 60049, 132847, 294931, 656877, 1467258, 3286218, 7378240, 16603458, 37441990, 84599854, 191501532, 434224404, 986161959, 2243009869, 5108859821

Offset: 0

Author

Paul Barry, Mar 14 2006

Keywords

• easy
• nonn

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

Examples

			1 + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 15*x^7 + 29*x^8 + 61*x^9 + ...
		

Links

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

Crossrefs

Cf. A007477.

Programs

Mathematica

Table[Sum[Binomial[k, n - 2*k]*CatalanNumber[k], {k, 0, Floor[n/2]}], {n, 0, 50}] (* G. C. Greubel, Feb 03 2017 *)

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 */

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