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

%I #140 Oct 28 2023 11:42:30

%S 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,

%T 40,31,20,10,4,1,1,5,15,35,65,101,135,155,155,135,101,65,35,15,5,1,1,

%U 6,21,56,120,216,336,456,546,580,546,456,336,216,120,56,21,6,1

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

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

%C Rows of A008287 mod 2 converted to decimal equals A177882. - _Vladimir Shevelev_, Jan 02 2011

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

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

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

%D B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 17.

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

%D 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).

%H Alois P. Heinz, <a href="/A008287/b008287.txt">Rows n = 0..100, flattened</a> (first 26 rows from T. D. Noe)

%H Moussa Ahmia and Hacene Belbachir, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v19i2p16/pdf">Preserving log-convexity for generalized Pascal triangles</a>, Electronic Journal of Combinatorics, 19(2) (2012), #P16. - _N. J. A. Sloane_, Oct 13 2012

%H Said Amrouche and Hacène Belbachir, <a href="https://arxiv.org/abs/2001.11665">Asymmetric extension of Pascal-Dellanoy triangles</a>, arXiv:2001.11665 [math.CO], 2020.

%H Armen G. Bagdasaryan and Ovidiu Bagdasar, <a href="https://doi.org/10.1016/j.endm.2018.05.012">On some results concerning generalized arithmetic triangles</a>, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 71-77.

%H Hacène Belbachir and Oussama Igueroufa, <a href="https://hal.archives-ouvertes.fr/hal-02918958/document#page=48">Combinatorial interpretation of bisnomial coefficients and Generalized Catalan numbers</a>, Proceedings of the 1st International Conference on Algebras, Graphs and Ordered Sets (ALGOS 2020), hal-02918958 [math.cs], 47-54.

%H Hacène Belbachir and Yassine Otmani, <a href="http://math.colgate.edu/~integers/x27/x27.pdf">Quadrinomial-Like Versions for Wolstenholme, Morley and Glaisher Congruences</a>, Integers (2023) Vol. 23.

%H Ji Young Choi, <a href="https://www.emis.de/journals/JIS/VOL22/Choi/choi15.html">Digit Sums Generalizing Binomial Coefficients</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.3.

%H Spiros D. Dafnis, Frosso S. Makri, and Andreas N. Philippou, <a href="http://www.fq.math.ca/Papers1/45-4/quartmakri04_2007.pdf">Restricted occupancy of s kinds of cells and generalized Pascal triangles</a>, Fibonacci Quart. 45 (2007), no. 4, 347-356.

%H L. Euler, <a href="https://arxiv.org/abs/math/0505425">On the expansion of the power of any polynomial (1+x+x^2+x^3+x^4+etc.)^n</a>, arXiv:math/0505425 [math.HO], 2005.

%H L. Euler, <a href="http://eulerarchive.maa.org/pages/E709.html">De evolutione potestatis polynomialis cuiuscunque (1+x+x^2+x^3+x^4+etc.)^n</a>, E709.

%H Nour-Eddine Fahssi, <a href="http://arxiv.org/abs/1202.0228">Polynomial Triangles Revisited</a>, arXiv:1202.0228 [math.CO], (25-July-2012).

%H D. C. Fielder and C. O. Alford, <a href="/A027907/a027907_2.pdf">Pascal's triangle: top gun or just one of the gang?</a>, Applications of Fibonacci Numbers 4 (1991), 77-90. (Annotated scanned copy)

%H J. E. Freund, <a href="http://www.jstor.org/stable/2308048">Restricted Occupancy Theory - A Generalization of Pascal's Triangle</a>, American Mathematical Monthly, Vol. 63, No. 1 (1956), pp. 20-27.

%H S. R. Finch, P. Sebah and Z.-Q. Bai, <a href="http://arXiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.

%H W. Florek and T. Lulek, <a href="http://www.mat.univie.ac.at/~slc/opapers/s26florek.html">Combinatorial analysis of magnetic configurations</a>, Séminaire Lotharingien de Combinatoire, B26d (1991), 12 pp.

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

%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.

%H Kantaphon Kuhapatanakul and Anantakitpaisal, <a href="https://doi.org/10.1080/23311835.2017.1333293">The k-nacci triangle and applications</a>, Cogent Math. 4, Article ID 1333293, 13 p. (2017).

%H T. Neuschel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Neuschel/neuschel4.html">A Note on Extended Binomial Coefficients</a>, J. Int. Seq. 17 (2014) # 14.10.4.

%H Jack Ramsay, <a href="/A349812/a349812.pdf">On Arithmetical Triangles</a>, The Pulse of Long Island, June 1965 [Mentions application to design of antenna arrays. Annotated scan.]

%H Claudia Smith and Verner E. Hoggatt, Jr. , <a href="http://www.fq.math.ca/Scanned/17-3/smith.pdf">A Study of the Maximal Values in Pascal's Quadrinomial Triangle</a>, Fibonacci Quart. 17 (1979), no. 3, 264-269.

%H Bao-Xuan Zhu, <a href="http://arxiv.org/abs/1605.00257">Linear transformations and strong q-log-concavity for certain combinatorial triangle</a>, arXiv preprint arXiv:1605.00257 [math.CO], 2016.

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

%F From _Vladimir Shevelev_, Dec 15 2010: (Start)

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

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

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

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

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

%F G.f.: 1/(1 - ( x + y*x + y^2*x +y^3*x )). - _Geoffrey Critzer_, Feb 05 2014

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

%e Triangle begins

%e 1;

%e 1,1,1,1;

%e 1,2,3,4,3,2,1;

%e 1,3,6,10,12,12,10,6,3,1; ...

%p #Define the r-nomial coefficients for r = 1, 2, 3, ...

%p rnomial := (r,n,k) -> add((-1)^i*binomial(n,i)*binomial(n+k-1-r*i,n-1), i = 0..floor(k/r)):

%p #Display the 4-nomials as a table

%p r := 4: rows := 10:

%p for n from 0 to rows do

%p seq(rnomial(r,n,k), k = 0..(r-1)*n)

%p end do;

%p # _Peter Bala_, Sep 07 2013

%p # second Maple program:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))((1+x+x^2+x^3)^n):

%p seq(T(n), n=0..10); # _Alois P. Heinz_, Aug 17 2018

%t Flatten[Table[CoefficientList[(1 + x + x^2 + x^3)^n, x], {n, 0, 10}]] (* _T. D. Noe_, Apr 04 2011 *)

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

%o (Maxima) quadrinomial(n,k):=coeff(expand((1+x+x^2+x^3)^n),x,k);

%o create_list(quadrinomial(n,k),n,0,8,k,0,3*n); /* _Emanuele Munarini_, Mar 15 2011 */

%o (Haskell)

%o a008287 n = a008287_list !! n

%o a008287_list = concat $ iterate ([1,1,1,1] *) [1]

%o instance Num a => Num [a] where

%o fromInteger k = [fromInteger k]

%o (p:ps) + (q:qs) = p + q : ps + qs

%o ps + qs = ps ++ qs

%o (p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs

%o _ * _ = []

%o -- _Reinhard Zumkeller_, Apr 02 2011

%Y Cf. A007318, A027907, A177882.

%K nonn,tabf,easy,nice

%O 0,7

%A _N. J. A. Sloane_