|
|
A005725
|
|
Quadrinomial coefficients.
(Formerly M2843)
|
|
12
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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) = 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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|