A005725 Quadrinomial coefficients.

1, 1, 3, 10, 31, 101, 336, 1128, 3823, 13051, 44803, 154518, 534964, 1858156, 6472168, 22597760, 79067375, 277164295, 973184313, 3422117190, 12049586631, 42478745781, 149915252028, 529606271560, 1872653175556, 6627147599476, 23471065878276, 83186110269928

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Examples

			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
		

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

Crossrefs

Cf. A008287.

Column k=3 of A305161.

Programs

Magma

P:=PolynomialRing(Integers()); [ Coefficients((1+x+x^2+x^3)^n)[n+1]: n in [0..25] ]; // Bruno Berselli, Jul 05 2011

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

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

PARI

a(n)=my(x='x); polcoeff((x^3+x^2+x+1)^n,n) \\ Charles R Greathouse IV, Feb 07 2017

Python

from math import comb
def A005725(n): return sum((-1 if k&1 else 1)*comb(n,k)*comb((n-(k<<1)<<1)-1,n-(k<<2)) for k in range((n>>2)+1)) if n else 1 # Chai Wah Wu, Aug 09 2025

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

Extensions

More terms from James Sellers, Jul 12 2000