%I #323 Oct 14 2024 12:27:31
%S 1,1,1,1,1,2,3,2,1,1,3,6,7,6,3,1,1,4,10,16,19,16,10,4,1,1,5,15,30,45,
%T 51,45,30,15,5,1,1,6,21,50,90,126,141,126,90,50,21,6,1,1,7,28,77,161,
%U 266,357,393,357,266,161,77,28,7,1,1,8,36,112,266
%N Triangle of trinomial coefficients T(n,k) (n >= 0, 0 <= k <= 2*n), read by rows: n-th row is obtained by expanding (1 + x + x^2)^n.
%C When the rows are centered about their midpoints, each term is the sum of the three terms directly above it (assuming the undefined terms in the previous row are zeros). - _N. J. A. Sloane_, Dec 23 2021
%C T(n,k) = number of integer strings s(0),...,s(n) such that s(0)=0, s(n)=k, s(i) = s(i-1) + c, where c is 0, 1 or 2. Columns of T include A002426, A005717 and A014531.
%C Also number of ordered trees having n+1 leaves, all at level three and n+k+3 edges. Example: T(3,5)=3 because we have three ordered trees with 4 leaves, all at level three and 11 edges: the root r has three children; from one of these children two paths of length two are hanging (i.e., 3 possibilities) while from each of the other two children one path of length two is hanging. Diagonal sums are the tribonacci numbers; more precisely: Sum_{i=0..floor(2*n/3)} T(n-i,i) = A000073(n+2). - _Emeric Deutsch_, Jan 03 2004
%C T(n,k) = A111808(n,k) for 0 <= k <= n and T(n, 2*n-k) = A111808(n,k) for 0 <= k < n. - _Reinhard Zumkeller_, Aug 17 2005
%C The trinomial coefficients, T(n,i), are the absolute value of the coefficients of the chromatic polynomial of P_2 X P_n factored with x*(x-1)^i terms. Example: The chromatic polynomial of P_2 X P_2 is: x*(x-1) - 2*x*(x-1)^2 + x*(x-1)^3 and so T(1,0)=1, T(1,1)=2 and T(1,1) = 1. - Thomas J. Pfaff (tpfaff(AT)ithaca.edu), Oct 02 2006
%C T(n,k) is the number of distinct ways in which k unlabeled objects can be distributed in n labeled urns allowing at most 2 objects to fall into each urn. - _N-E. Fahssi_, Mar 16 2008
%C T(n,k) is the number of compositions of k into n parts p, each part 0 <= p <= 2. 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 <= 3. E.g., T(2,3)=2 since 5 = 3+2 = 2+3. - _Steffen Eger_, Jun 10 2011
%C Number of lattice paths from (0,0) to (n,k) using steps (1,0), (1,1), (1,2). - _Joerg Arndt_, Jul 05 2011
%C Number of lattice paths from (0,0) to (2*n-k,k) using steps (2,0), (1,1), (0,2). - _Werner Schulte_, Jan 25 2017
%C T(n,k) is number of distinct ways to sum the integers -1, 0 , and 1 n times to obtain n-k, where T(n,0) = T(n,2*n+1) = 1. - _William Boyles_, Apr 23 2017
%C T(n-1,k-1) is the number of 2-compositions of n with 0's having k parts; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 15 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. Carlitz, Comment on the paper "Some probability distributions and their associated structures", Math. Magazine, 37:1 (1964), 51-52. [The triangle is on page 51]
%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).
%D L. Kleinrock, Uniform permutation of sequences, JPL Space Programs Summary, Vol. 37-64-III, Apr 30, 1970, pp. 32-43.
%H Seiichi Manyama, <a href="/A027907/b027907.txt">Rows n=0..99 of triangle, flattened</a> (Rows 0..30 from T. D. Noe)
%H Moussa Ahmia and Hacene Belbachir, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p16">Preserving log-convexity for generalized Pascal triangles</a>, Electronic Journal of Combinatorics, 19(2) (2012), #P16. - _N. J. A. Sloane_, Oct 13 2012
%H Tewodros Amdeberhan, Moa Apagodu and Doron Zeilberger, <a href="http://arxiv.org/abs/1507.07660">Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle</a>, arXiv:1507.07660 [math.CO], 2015.
%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 G. E. Andrews, <a href="http://dx.doi.org/10.1090/S0894-0347-1990-1040390-4">Euler's 'exemplum memorabile inductionis fallacis' and q-trinomial coefficients</a>, J. Amer. Math. Soc. 3 (1990) 653-669.
%H G. E. Andrews, <a href="http://www.mat.univie.ac.at/~slc/opapers/s25andrews.html">Three aspects of partitions</a>, Séminaire Lotharingien de Combinatoire, B25f (1990), 1 p.
%H George E. Andrews and Alexander Berkovich, <a href="https://arxiv.org/abs/q-alg/9702008">A trinomial analogue of Bailey's lemma and N= 2 superconformal invariance</a>, arXiv:q-alg/9702008, 1997; Communications in mathematical physics 192.2 (1998): 245-260. See page 248.
%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 Abdelghafour Bazeniar, Moussa Ahmia and Hacène Belbachir, <a href="https://doi.org/10.3906/mat-1705-27">Connection between bi^s nomial coefficients with their analogs and symmetric functions</a>, Turkish Journal of Mathematics, Vol. 42, No. 3 (2018), pp. 807-818.
%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 Leonardo Bennun, <a href="http://arxiv.org/abs/1603.02061">A Pragmatic Smoothing Method for Improving the Quality of the Results in Atomic Spectroscopy</a>, arXiv:1603.02061 [physics.atom-ph], 2016. See reference 22.
%H Alexander Berkovich and Ali K. Uncu, <a href="https://arxiv.org/abs/1810.06497">Elementary Polynomial Identities Involving q-Trinomial Coefficients</a>, arXiv:1810.06497 [math.NT], 2018.
%H F. R. Bernhart, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discr. Math., 204 (1999) 73-112.
%H Jan Bok, <a href="https://arxiv.org/abs/1801.05498">Graph-indexed random walks on special classes of graphs</a>, arXiv:1801.05498 [math.CO], 2018.
%H Richard C. Bollinger, <a href="https://www.jstor.org/stable/2690294">Reliability and Runs of Ones</a>, Mathematics Magazine, 57(1) (1984), 34-37.
%H B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. <a href="http://www.fq.math.ca/pascal.html">English translation</a> published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 17.
%H Eduardo H. M. Brietzke, <a href="http://www.fq.math.ca/Papers1/44-2/quarteduardobrietzke02_2006.pdf">Generalization of an identity of Andrews</a>, Fibonacci Quart. 44(2) (2006), 166-171.
%H Rezig Boualam and Moussa Ahmia, <a href="https://arxiv.org/abs/2409.18886">Log-concavity and strong q-log-convexity for some generalized triangular arrays</a>, arXiv:2409.18886 [math.CO], 2024. See p. 2.
%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. 22 (2019), Article 19.8.3.
%H Karl Dilcher and Larry Ericksen, <a href="https://arxiv.org/abs/2405.12024">Polynomials and algebraic curves related to certain binary and b-ary overpartitions</a>, arXiv:2405.12024 [math.CO], 2024. See p. 7.
%H S. Eger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Eger/eger11.html">Some Elementary Congruences for the Number of Weighted Integer Compositions</a>, J. Int. Seq. 18 (2015), #15.4.1.
%H L. Euler, <a href="https://arxiv.org/abs/1202.0028">Disquitiones analyticae super evolutione potestatis trinomialis (1+x+xx)^n</a>, 1805. This is paper E722 in Eneström's index of Euler's works, translated from Latin to German. The sequence appears in the table on page 2.
%H L. Euler, <a href="http://arXiv.org/abs/math.HO/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], 2012.
%H Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, arXiv:1203.6792 [math.CO], 2012 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">J. Int. Seq., 17 (2014), #14.1.5</a>.
%H D. Fielder, <a href="/A027907/a027907_1.pdf">Letter to N. J. A. Sloane, Jun. 1991</a>.
%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 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 A. Fink, R. K. Guy and M. Krusemeyer, <a href="https://doi.org/10.11575/cdm.v3i2.61940">Partitions with parts occurring at most thrice</a>, Contrib. Discr. Math. 3(2) (2008), 76-114.
%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 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(1) (1956), 20-27.
%H Berit Nilsen Givens, <a href="https://doi.org/10.1080/17513472.2023.2197832">The trinomial triangle knitted shawl</a>, J. Math. Arts (2023).
%H Fern Gossow, <a href="https://arxiv.org/abs/2410.05678">Lyndon-like cyclic sieving and Gauss congruence</a>, arXiv:2410.05678 [math.CO], 2024. See p. 17.
%H R. K. Guy, <a href="/A005712/a005712.pdf">Letter to N. J. A. Sloane, 1987</a>
%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="http://www.fq.math.ca/Scanned/7-4/hoggatt-a.pdf">Diagonal sums of generalized Pascal triangles</a>, Fib. Quart. 7 (1969), 341-358 and 393.
%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 Veronika Irvine, <a href="http://hdl.handle.net/1828/7495">Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns</a>, PhD Dissertation, University of Victoria, 2016.
%H S. Kak, <a href="http://arxiv.org/abs/physics/0411195">The Golden Mean and the Physics of Aesthetics</a>, arXiv:physics/0411195 [physics.hist-ph], 2004.
%H L. Kleinrock, <a href="/A027907/a027907.pdf">Uniform permutation of sequences</a>, JPL Space Programs Summary, Vol. 37-64-III, Apr 30, 1970, pp. 32-43. [Annotated scanned copy]
%H László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Nemeth/nemeth6.html">The trinomial transform triangle</a>, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also <a href="https://arxiv.org/abs/1807.07109">arXiv:1807.07109</a> [math.NT], 2018.
%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 L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson, <a href="http://dx.doi.org/10.1016/0166-218X(91)90088-E">The Riordan group</a>, Discrete Applied Math., 34 (1991), 229-239.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrinomialTriangle.html">Trinomial Triangle</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrinomialCoefficient.html">Trinomial Coefficient</a>.
%H Sheng-Liang Yang and Yuan-Yuan Gao, <a href="https://www.fq.math.ca/Papers1/56-4/yanggao1032018.pdf">The Pascal rhombus and Riordan arrays</a>, Fib. Q., 56:4 (2018), 337-347. See Fig. 3.
%H Xuxu Zhao, Xu Wang and Haiyuan Yao, <a href="https://arxiv.org/abs/1905.00573">Some enumerative properties of a class of Fibonacci-like cubes</a>, arXiv:1905.00573 [math.CO], 2019.
%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:1605.00257 [math.CO], 2016.
%F G.f.: 1/(1-z*(1+w+w^2)).
%F T(n,k) = Sum_{r=0..floor(k/3)} (-1)^r*binomial(n, r)*binomial(k-3*r+n-1, n-1)).
%F Recurrence: T(0,0) = 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k-0), with T(n,k) = 0 if k < 0 or k > 2*n:
%F T(i,0) = T(i, 2*i) = 1 for i >= 0, T(i, 1) = T(i, 2*i-1) = i for i >= 1 and for i >= 2 and 2 <= j <= i-2, T(i, j) = T(i-1, j-2) + T(i-1, j-1) + T(i-1, j).
%F The row sums are powers of 3 (A000244). - _Gerald McGarvey_, Aug 14 2004
%F T(n,k) = Sum_{i=0..floor(k/2)} binomial(n, 2*i+n-k) * binomial(2*i+n-k, i). - _Ralf Stephan_, Jan 26 2005
%F T(n,k) = Sum_{j=0..n} binomial(n, j) * binomial(j, k-j). - _Paul Barry_, May 21 2005
%F T(n,k) = Sum_{j=0..n} binomial(k-j, j) * binomial(n, k-j). - _Paul Barry_, Nov 04 2005
%F From Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006: (Start)
%F T(n,k) = Sum_{j=0..n} (-1)^j * binomial(n,j) * binomial(2*n-2*j, k-j); (G. E. Andrews (1990)) obtained by expanding ((1+x)^2 - x)^n.
%F T(n,k) = Sum_{j=0..n} binomial(n,j) * binomial(n-j, k-2*j); obtained by expanding ((1+x) + x^2)^n.
%F T(n,k) = (-1)^k*Sum_{j=0..n} (-3)^j * binomial(n,j) * binomial(2*n-2*j, k-j); obtained by expanding ((1-x)^2 + 3*x)^n.
%F T(n,k) = (1/2)^k * Sum_{j=0..n} 3^j * binomial(n,j) * binomial(2*n-2*j, k-2*j); obtained by expanding ((1+x/2)^2 + (3/4)*x^2)^n.
%F T(n,k) = (2^k/4^n) * Sum_{j=0..n} 3^j * binomial(n,j) * binomial(2*n-2*j, k); obtained by expanding ((1/2+x)^2 + 3/4)^n using T(n,k) = T(2*n-k). (End)
%F From _Paul D. Hanna_, Apr 18 2012: (Start)
%F Let A(x) be the g.f. of the flattened sequence, then:
%F G.f.: A(x) = Sum_{n>=0} x^(n^2) * (1+x+x^2)^n.
%F G.f.: A(x) = Sum_{n>=0} x^n*(1+x+x^2)^n * Product_{k=1..n} (1 - (1+x+x^2) * x^(4*k-3)) / (1 - (1+x+x^2)*x^(4*k-1)).
%F G.f.: A(x) = 1/(1 - x*(1+x+x^2)/(1 + x*(1-x^2)*(1+x+x^2)/(1 - x^5*(1+x+x^2)/(1 + x^3*(1-x^4)*(1+x+x^2)/(1 - x^9*(1+x+x^2)/(1 + x^5*(1-x^6)*(1+x+x^2)/(1 - x^13* (1+x+x^2)/(1 + x^7*(1-x^8)*(1+x+x^2)/(1 - ...))))))))), a continued fraction.
%F (End)
%F Triangle: G.f. = Sum_{n>=0} (1+x+x^2)^n * x^(n^2) * y^n. - _Daniel Forgues_, Mar 16 2015
%F From _Peter Luschny_, May 08 2016: (Start)
%F T(n+1,n)/(n+1) = A001006(n) (Motzkin) for n>=0.
%F T(n,k) = H(n, k) if k < n else H(n, 2*n-k) where H(n,k) = binomial(n,k)* hypergeom([(1-k)/2, -k/2], [n-k+1], 4)).
%F T(n,k) = GegenbauerC(m, -n, -1/2) where m=k if k < n else 2*n-k. (End)
%F T(n,k) = (-1)^k * C(2*n,k) * hypergeom([-k, -(2*n-k)], [-n+1/2], 3/4), for all k with 0 <= k <= 2n. - _Robert S. Maier_, Jun 13 2023
%F T(n,n) = Sum_{k=0..2*n} (-1)^k*(T(n,k))^2 and T(2*n,2*n) = Sum_{k=0..2*n} (T(n,k))^2 for n >= 0. - _Werner Schulte_, Nov 08 2016
%F T(n,n) = A002426(n), central trinomial coefficients. - _M. F. Hasler_, Nov 02 2019
%F Sum_{k=0..n-1} T(n, 2*k) = (3^n-1)/2. - _Tony Foster III_, Oct 06 2020
%e The triangle T(n, k) begins:
%e n\k 0 1 2 3 4 5 6 7 8 9 10 11 12
%e 0: 1
%e 1: 1 1 1
%e 2: 1 2 3 2 1
%e 3: 1 3 6 7 6 3 1
%e 4: 1 4 10 16 19 16 10 4 1
%e 5: 1 5 15 30 45 51 45 30 15 5 1
%e 6: 1 6 21 50 90 126 141 126 90 50 21 6 1
%e Concatenated rows:
%e G.f. = 1 + (x^2+x+1)*x + (x^2+x+1)^2*x^4 + (x^2+x+1)^3*x^9 + ...
%e = 1 + (x + x^2 + x^3) + (x^4 + 2*x^5 + 3*x^6 + 2*x^7 + x^8) +
%e (x^9 + 3*x^10 + 6*x^11 + 7*x^12 + 6*x^13 + 3*x^14 + x^15) + ... .
%e As a centered triangle, this begins:
%e ...........1...........
%e ........1..1..1........
%e .....1..2..3..2..1.....
%e ..1..3..6..7..6..3..1..
%e ......
%p A027907 := proc(n,k) expand((1+x+x^2)^n) ; coeftayl(%,x=0,k) ; end proc:
%p seq(seq(A027907(n,k),k=0..2*n),n=0..5) ; # _R. J. Mathar_, Jun 13 2011
%p T := (n,k) -> simplify(GegenbauerC(`if`(k<n,k,2*n-k), -n, -1/2));
%p for n from 0 to 8 do seq(T(n,k),k=0..2*n) od; # _Peter Luschny_, May 08 2016
%t Table[CoefficientList[Series[(Sum[x^i, {i, 0, 2}])^n, {x, 0, 2 n}], x], {n, 0, 10}] // Grid (* _Geoffrey Critzer_, Mar 31 2010 *)
%t Table[Sum[Binomial[n, i]Binomial[n - i, k - 2i], {i, 0, n}], {n, 0, 10}, {k, 0, 2n}] (* _Adi Dani_, May 07 2011 *)
%t T[ n_, k_] := If[ n < 0, 0, Coefficient[ (1 + x + x^2)^n, x, k]]; (* _Michael Somos_, Nov 08 2016 *)
%t Flatten[DeleteCases[#,0]&/@CellularAutomaton[{Total[#] &, {}, 1}, {{1}, 0}, 8] ] (* _Giorgos Kalogeropoulos_, Nov 09 2021 *)
%o (PARI) {T(n, k) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, k))}; /* _Michael Somos_, Jun 27 2003 */
%o (Maxima) trinomial(n,k):=coeff(expand((1+x+x^2)^n),x,k);
%o create_list(trinomial(n,k),n,0,8,k,0,2*n); \\ _Emanuele Munarini_, Mar 15 2011
%o (Maxima) create_list(ultraspherical(k,-n,-1/2),n,0,6,k,0,2*n); /* _Emanuele Munarini_, Oct 18 2016 */
%o (Haskell)
%o a027907 n k = a027907_tabf !! n !! k
%o a027907_row n = a027907_tabf !! n
%o a027907_tabf = [1] : iterate f [1, 1, 1] where
%o f row = zipWith3 (((+) .) . (+))
%o (row ++ [0, 0]) ([0] ++ row ++ [0]) ([0, 0] ++ row)
%o a027907_list = concat a027907_tabf
%o -- _Reinhard Zumkeller_, Jul 06 2014, Jan 22 2013, Apr 02 2011
%Y Columns of T include A002426, A005717, A014531, A005581, A005712, etc. See also A035000, A008287.
%Y First differences are in A025177. Pairwise sums are in A025564.
%Y Cf. A007318 (Pascal's triangle); A000073, A001006, A123531, A055217, A027908, A027913, A027914, A027023.
%K nonn,tabf,nice,easy,changed
%O 0,6
%A _N. J. A. Sloane_