login
Quadrinomial coefficients.
(Formerly M2843)
12

%I M2843 #75 Mar 21 2023 09:22:17

%S 1,1,3,10,31,101,336,1128,3823,13051,44803,154518,534964,1858156,

%T 6472168,22597760,79067375,277164295,973184313,3422117190,12049586631,

%U 42478745781,149915252028,529606271560,1872653175556,6627147599476,23471065878276,83186110269928

%N Quadrinomial coefficients.

%C Coefficient of x^n in (1+x+x^2+x^3)^n.

%C 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

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A005725/b005725.txt">Table of n, a(n) for n = 0..200</a>

%H R. K. Guy, <a href="/A005712/a005712.pdf">Letter to N. J. A. Sloane, 1987</a>

%F 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

%F 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

%F 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

%F 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

%F a(n) = A008287(n, n). - _Sean A. Irvine_, Aug 15 2016

%F a(n) = hypergeom([1/2-n/2, -n, -n/2], [1/2, 1], -1). - _Vladimir Reshetnikov_, Oct 04 2016

%F From _Peter Bala_, Mar 31 2020: (Start)

%F a(n) = Sum_{k = 0..floor(n/4)} (-1)^k*C(n,k)*C(2*n-4*k-1,n-4*k).

%F 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.

%F 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)

%F a(n) = Sum_{k = 0.. floor(n/2)} binomial(n,k)*binomial(n,2*k). - _Peter Bala_, Mar 16 2023

%e 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

%p 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

%p a := n -> add(binomial(n,j)*binomial(n,2*j),j=0..n): seq(a(n), n=1..25); # _Zerinvary Lajos_, Feb 12 2007

%p 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

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

%t Table[HypergeometricPFQ[{1/2 - n/2, -n, -n/2}, {1/2, 1}, -1], {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 04 2016 *)

%o (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

%o (Magma) P<x>:=PolynomialRing(Integers()); [ Coefficients((1+x+x^2+x^3)^n)[n+1]: n in [0..25] ]; // _Bruno Berselli_, Jul 05 2011

%o (PARI) a(n)=my(x='x); polcoeff((x^3+x^2+x+1)^n,n) \\ _Charles R Greathouse IV_, Feb 07 2017

%Y Cf. A008287.

%Y Column k=3 of A305161.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Jul 12 2000