A008287 Triangle of quadrinomial coefficients, row n is the sequence of coefficients of (1 + x + x^2 + x^3)^n.

1, 1, 1, 1, 1, 1, 2, 3, 4, 3, 2, 1, 1, 3, 6, 10, 12, 12, 10, 6, 3, 1, 1, 4, 10, 20, 31, 40, 44, 40, 31, 20, 10, 4, 1, 1, 5, 15, 35, 65, 101, 135, 155, 155, 135, 101, 65, 35, 15, 5, 1, 1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabf
• easy
• nice

Comments

Coefficient of x^k in (1 + x + x^2 + x^3)^n is the number of distinct ways in which k unlabeled objects can be distributed in n labeled urns allowing at most 3 objects to fall in each urn. - N-E. Fahssi, Mar 16 2008

Rows of A008287 mod 2 converted to decimal equals A177882. - Vladimir Shevelev, Jan 02 2011

T(n,k) is the number of compositions of k into n parts p, each part 0<=p<=3. Adding 1 to each part, as a corollary, T(n,k) is the number of compositions of n+k into n parts p where 1<=p<=4. E.g., T(2,3)=4 since 3=0+3=3+0=1+2=2+1. In general, the entry (n,k) of the (l+1)-nomial triangle gives the number of compositions of k into n parts p, each part 0<=p<=l. - Steffen Eger, Jun 18 2011

Number of lattice paths from (0,0) to (n,k) using steps (1,0), (1,1), (1,2), (1,3). - Joerg Arndt, Jul 05 2011

T(n-1,k-1) is the number of 3-compositions of n with zeros having k parts; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020

T(n,k) is the number of ways to obtain a sum of n+k when throwing a 4-sided die n times. Follows from the "T(n,k) is the number of compositions of n+k into n parts p where 1 <= p <= 4" comment above. - Feryal Alayont, Dec 30 2024

Examples

			Triangle begins
  1;
  1,1,1,1;
  1,2,3,4,3,2,1;
  1,3,6,10,12,12,10,6,3,1; ...
		

References

• Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
• D. C. Fielder and C. O. Alford, Pascal's triangle: top gun or just one of the gang?, in G E Bergum et al., eds., Applications of Fibonacci Numbers Vol. 4 1991 pp. 77-90 (Kluwer).

Links

• Alois P. Heinz, Rows n = 0..100, flattened (first 26 rows from T. D. Noe)
• Moussa Ahmia and Hacene Belbachir, Preserving log-convexity for generalized Pascal triangles, Electronic Journal of Combinatorics, 19(2) (2012), #P16. - _N. J. A. Sloane_, Oct 13 2012
• Said Amrouche and Hacène Belbachir, Asymmetric extension of Pascal-Dellanoy triangles, arXiv:2001.11665 [math.CO], 2020.
• Armen G. Bagdasaryan and Ovidiu Bagdasar, On some results concerning generalized arithmetic triangles, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 71-77.
• Hacène Belbachir and Oussama Igueroufa, Combinatorial interpretation of bisnomial coefficients and Generalized Catalan numbers, Proceedings of the 1st International Conference on Algebras, Graphs and Ordered Sets (ALGOS 2020), hal-02918958 [math.cs], 47-54.
• Hacène Belbachir and Yassine Otmani, Quadrinomial-Like Versions for Wolstenholme, Morley and Glaisher Congruences, Integers (2023) Vol. 23.
• Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 17.
• Ji Young Choi, Digit Sums Generalizing Binomial Coefficients, J. Int. Seq., Vol. 22 (2019), Article 19.8.3.
• Spiros D. Dafnis, Frosso S. Makri, and Andreas N. Philippou, Restricted occupancy of s kinds of cells and generalized Pascal triangles, Fibonacci Quart. 45 (2007), no. 4, 347-356.
• L. Euler, On the expansion of the power of any polynomial (1+x+x^2+x^3+x^4+etc.)^n, arXiv:math/0505425 [math.HO], 2005.
• L. Euler, De evolutione potestatis polynomialis cuiuscunque (1+x+x^2+x^3+x^4+etc.)^n, E709.
• Nour-Eddine Fahssi, Polynomial Triangles Revisited, arXiv:1202.0228 [math.CO], (25-July-2012).
• D. C. Fielder and C. O. Alford, Pascal's triangle: top gun or just one of the gang?, Applications of Fibonacci Numbers 4 (1991), 77-90. (Annotated scanned copy)
• J. E. Freund, Restricted Occupancy Theory - A Generalization of Pascal's Triangle, American Mathematical Monthly, Vol. 63, No. 1 (1956), pp. 20-27.
• S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
• W. Florek and T. Lulek, Combinatorial analysis of magnetic configurations, Séminaire Lotharingien de Combinatoire, B26d (1991), 12 pp.
• R. K. Guy, Letter to N. J. A. Sloane, 1987
• Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
• Kantaphon Kuhapatanakul and Anantakitpaisal, The k-nacci triangle and applications, Cogent Math. 4, Article ID 1333293, 13 p. (2017).
• Thorsten Neuschel, A Note on Extended Binomial Coefficients, J. Int. Seq. 17 (2014) # 14.10.4.
• Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 4.
• Jack Ramsay, On Arithmetical Triangles, The Pulse of Long Island, June 1965 [Mentions application to design of antenna arrays. Annotated scan.]
• Boualam Rezig and Moussa Ahmia, Combinatorics of three-Catalan numbers and some positivities, arXiv:2502.03615 [math.CO], 2025. See Table 1 p. 4.
• Claudia Smith and Verner E. Hoggatt, Jr. , A Study of the Maximal Values in Pascal's Quadrinomial Triangle, Fibonacci Quart. 17 (1979), no. 3, 264-269.
• Bao-Xuan Zhu, Linear transformations and strong q-log-concavity for certain combinatorial triangle, arXiv preprint arXiv:1605.00257 [math.CO], 2016.

Crossrefs

Cf. A007318, A027907, A177882.

Programs

Haskell

a008287 n = a008287_list !! n
a008287_list = concat $ iterate ([1,1,1,1] *) [1]
instance Num a => Num [a] where
   fromInteger k = [fromInteger k]
   (p:ps) + (q:qs) = p + q : ps + qs
   ps + qs         = ps ++ qs
   (p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs
    *                = []
-- Reinhard Zumkeller, Apr 02 2011

Maple

#Define the r-nomial coefficients for r = 1, 2, 3, ...
rnomial := (r,n,k) -> add((-1)^i*binomial(n,i)*binomial(n+k-1-r*i,n-1), i = 0..floor(k/r)):
#Display the 4-nomials as a table
r := 4:  rows := 10:
for n from 0 to rows do
seq(rnomial(r,n,k), k = 0..(r-1)*n)
end do;
# Peter Bala, Sep 07 2013
# second Maple program:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))((1+x+x^2+x^3)^n):
seq(T(n), n=0..10);  # Alois P. Heinz, Aug 17 2018

Mathematica

Flatten[Table[CoefficientList[(1 + x + x^2 + x^3)^n, x], {n, 0, 10}]] (* T. D. Noe, Apr 04 2011 *)
T[n_, k_] := Sum[Binomial[n, i] Binomial[n, k-2i], {i, 0, k/2}]; Table[T[n, k], {n, 0, 6}, {k, 0, 3n}] // Flatten (* Jean-François Alcover, Feb 02 2018 *)

Maxima

quadrinomial(n,k):=coeff(expand((1+x+x^2+x^3)^n),x,k);
create_list(quadrinomial(n,k),n,0,8,k,0,3*n); /* Emanuele Munarini, Mar 15 2011 */

Formula

n-th row is formed by expanding (1+x+x^2+x^3)^n.

From Vladimir Shevelev, Dec 15 2010: (Start)

T(n,0) = 1; T(n,3*n) = 1; T(n,k) = T(n,3*n-k);

T(n,k) = 0, iff k<0 or k>3*n; Sum{k=0..3*n} T(n,k) = 4^n; Sum{k=0..3*n}((-1)^k)*T(n,k)=0 for n > 0; [corrected by Werner Schulte, Sep 09 2015]

T(n,k) = Sum{i=0..floor(k/2)} C(n,i)*C(n,k-2*i);

T(n+1,k) = T(n,k-3)+T(n,k-2)+T(n,k-1)+T(n,k). (End)

T(n,k) = Sum_{i = 0..floor(k/4)} (-1)^i*C(n,i)*C(n+k-1-4*i,n-1) for n >= 0 and 0 <= k <= 3*n. - Peter Bala, Sep 07 2013

G.f.: 1/(1 - ( x + y*x + y^2*x +y^3*x )). - Geoffrey Critzer, Feb 05 2014

T(n,k) = Sum_{j=0..k} (-2)^j*binomial(n,j)*binomial(3*n-2*j,k-j) for n >= 0 and 0 <= k <= 3*n (conjectured). - Werner Schulte, Sep 09 2015