OFFSET
0,3
COMMENTS
Coefficient of x^n in (1+x+x^2+x^3)^n.
Number of lattice paths from (0,0) to (n,n) using steps (1,0), (1,1), (1,2), (1,3). - Joerg Arndt, Jul 05 2011
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
T. D. Noe, Table of n, a(n) for n = 0..200
R. K. Guy, Letter to N. J. A. Sloane, 1987
FORMULA
a(n) = sum(i+j+k=n, 0<=k<=j<=i<=n, C(n,i)*C(i,j)*C(j,k)). - Benoit Cloitre, Jun 06 2004
G.f.: A(x) where (16*x^3+8*x^2+11*x-4)*A(x)^3+(3-2*x)*A(x)+1 = 0. - Mark van Hoeij, Apr 30 2013
Recurrence: 2*n*(2*n-1)*(13*n-19)*a(n) = (143*n^3 - 352*n^2 + 251*n - 54)*a(n-1) + 4*(n-1)*(26*n^2 - 51*n + 15)*a(n-2) + 16*(n-2)*(n-1)*(13*n-6)*a(n-3). - Vaclav Kotesovec, Aug 10 2013
a(n) ~ sqrt((39+7*39^(2/3)/c+39^(1/3)*c)/156) * ((b+11+217/b)/12)^n/sqrt(Pi*n), where b = (6371+624*sqrt(78))^(1/3), c = (117+2*sqrt(78))^(1/3). - Vaclav Kotesovec, Aug 10 2013
a(n) = A008287(n, n). - Sean A. Irvine, Aug 15 2016
a(n) = hypergeom([1/2-n/2, -n, -n/2], [1/2, 1], -1). - Vladimir Reshetnikov, Oct 04 2016
From Peter Bala, Mar 31 2020: (Start)
a(n) = Sum_{k = 0..floor(n/4)} (-1)^k*C(n,k)*C(2*n-4*k-1,n-4*k).
a(p) == 1 (mod p^2) for any prime p >= 3. More generally, we may have a(p^k) == a(p^(k-1)) (mod p^(2*k)) for k >= 2 and any prime p >= 3.
The sequence defined by b(n) := [x^n] ( F(x)/F(-x) )^n, where F(x) = 1 + x + x^2 + x^3, may satisfy the stronger supercongruences b(p) == 2 (mod p^3) for prime p >= 5 (checked up to p = 499). (End)
a(n) = Sum_{k = 0.. floor(n/2)} binomial(n,k)*binomial(n,2*k). - Peter Bala, Mar 16 2023
EXAMPLE
For n=2, (x^3 + x^2 + x + 1)^2 = x^6 + 2x^5 + 3x^4 + 4x^3 + 3x^2 + 2x + 1, and the coefficient of x^n = x^2 is 3, so a(2) = 3. - Michael B. Porter, Aug 15 2016
MAPLE
seq(add(binomial(n, 2*k)*binomial(n, k), k=0..floor(n/2)), n=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
a := n -> add(binomial(n, j)*binomial(n, 2*j), j=0..n): seq(a(n), n=1..25); # Zerinvary Lajos, Feb 12 2007
seq(coeff(series(RootOf((16*x^3+8*x^2+11*x-4)*A^3+(3-2*x)*A+1, A), x=0, n+1), x, n), n=0..30); # Mark van Hoeij, Apr 30 2013
MATHEMATICA
a[n_] := Coefficient[(1+x+x^2+x^3)^n, x^n]; a[0] = 1; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 15 2011 *)
Table[HypergeometricPFQ[{1/2 - n/2, -n, -n/2}, {1/2, 1}, -1], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 04 2016 *)
PROG
(Maxima) quadrinomial(n, k):=coeff(expand((1+x+x^2+x^3)^n), x, k); makelist(quadrinomial(n, n), n, 0, 12); /* Emanuele Munarini, Mar 15 2011 */
(Magma) P<x>:=PolynomialRing(Integers()); [ Coefficients((1+x+x^2+x^3)^n)[n+1]: n in [0..25] ]; // Bruno Berselli, Jul 05 2011
(PARI) a(n)=my(x='x); polcoeff((x^3+x^2+x+1)^n, n) \\ Charles R Greathouse IV, Feb 07 2017
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from James A. Sellers, Jul 12 2000
STATUS
approved