login
A116411
Coefficient of x^n in the expansion of (1+x+x^3)^n.
8
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,4
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
Hacène Belbachir, Abdelghani Mehdaoui, Diagonal sums in Pascal pyramid (1, 2, r), Les Annales RECITS (2019) Vol. 6, 45-52.
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
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 *)
PROG
(PARI) a(n)=polcoeff((1+x+x^3)^n, n); /* Joerg Arndt, Jul 01 2011 */
CROSSREFS
Cf. A071879.
Sequence in context: A011937 A307304 A097122 * A333047 A376804 A106337
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Feb 13 2006
STATUS
approved