A116411 Coefficient of x^n in the expansion of (1+x+x^3)^n.

1, 1, 1, 4, 13, 31, 76, 211, 589, 1597, 4351, 12046, 33496, 93094, 259351, 725089, 2031709, 5701189, 16023181, 45104044, 127134283, 358764613, 1013494318, 2865933907, 8111573416, 22977551656, 65138143006, 184789086106, 524571000799, 1490044262503, 4234901256781, 12042611698876, 34262320521661, 97525522430989

Offset: 0

Author

Paul Barry, Feb 13 2006

Keywords

• easy
• nonn

Comments

Binomial transform of central coefficient of (1+x^3)^n.

Number of lattice paths from (0,0) to (n,n) using steps (1,0), (1,1), (1,3). [Joerg Arndt, Jul 05 2011]

a(n) also gives the number of lattice paths from (0,0) to (n,2*n) using steps (1,0), (1,2) and (1,3) since if a*(1,0) + b*(1,1) + c*(1,3) denotes a path from (0,0) to (n,n) then c*(1,0) + b*(1,2) + a*(1,3) is a path from (0,0) to (n,2*n) and vice versa. - Peter Bala, Jul 20 2014

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• Hacène Belbachir, Abdelghani Mehdaoui, Diagonal sums in Pascal pyramid (1, 2, r), Les Annales RECITS (2019) Vol. 6, 45-52.

Crossrefs

Cf. A071879.

Programs

Maple

series(RootOf( (31*x^3-12*x^2+12*x-4)*A^3+(3-3*x)*A+1, A),x=0,30); # Mark van Hoeij, Apr 16 2013

Mathematica

Flatten[{1,Table[Coefficient[Expand[(1+x+x^3)^n],x^n],{n,1,20}]}] (* Vaclav Kotesovec, Feb 11 2015 *)
Table[HypergeometricPFQ[{1/3-n/3,2/3-n/3,-n/3},{1/2,1},-27/4],{n,0,20}] (* Benedict W. J. Irwin, Nov 01 2016 *)

PARI

a(n)=polcoeff((1+x+x^3)^n,n); /* Joerg Arndt, Jul 01 2011 */

Formula

a(n) = Sum_{k=0..floor(n/3)} C(n, 3*k)*C(3*k, k).

a(n) = Sum_{k=0..n} C(n, k)*C(k, k/3)*(cos(2*Pi*k/3)+1/2)*2/3.

G.f.: A(x) satisfies (31*x^3-12*x^2+12*x-4)*A(x)^3+(3-3*x)*A(x)+1 = 0. - Mark van Hoeij, Apr 16 2013

From Peter Bala, Jul 20 2014: (Start)

a(n) = coefficient of x^(2*n) in the expansion of (1 + x^2 + x^3)^n.

O.g.f.: sum {n >= 0} binomial(3*n,n)*x^(3*n)/(1 - x)^(3*n + 1).

By the Lagrange inversion formula, the o.g.f. equals the logarithmic derivative of the o.g.f. of A071879.

E.g.f.: exp(x)*sum {n >= 0} x^(3*n)/((2*n)!*n!). (End)

Recurrence: 2*n*(2*n-3)*a(n) = 2*(6*n^2 - 12*n + 5)*a(n-1) - 6*(n-1)*(2*n-3)*a(n-2) + 31*(n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Feb 11 2015

a(n) ~ (3 + 2^(2/3))^(n+1/2) / (2^(2*n/3 + 1) * sqrt(3*Pi*n)). - Vaclav Kotesovec, Feb 11 2015

a(n) = 3F2[1/3-n/3,2/3-n/3,-n/3; 1/2,1; -27/4]. - Benedict W. J. Irwin, Nov 01 2016