TOPICS
Search

Trinomial Coefficient

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A trinomial coefficient (n; k)_2 is the coefficient of x^(n+k) in the expansion of (1+x+x^2)^n, where n is a nonnegative integer and k is an integer with -n<=k<=n (Andrews 1990). Set (n; k)_2=0 for |k|>n. The coefficients satisfy

(n; -k)_2=(n; k)_2.
(1)

The trinomial coefficient can be given by the closed form

(n; k)_2={1 for n=k=0; C_(k+n)^((-n))(-1/2) otherwise,
(2)

where C_n^((lambda))(z) is a Gegenbauer polynomial.

Equivalently, the trinomial coefficients are defined by

(1+x+x^(-1))^n=sum_(k=-n)^n(n; k)_2x^k.
(3)

The trinomial coefficients also have generating function

f(w,z)=1/(1-z(1+w+w^2))
(4)
=1+z(1+w+w^2)+z^2(1+2w+3w^2+2w^3+w^4)+...,
(5)

i.e.,

sum_(n=0)^inftysum_(k=-n)^n(n; -k)_2z^nw^(k+n)=1/(1-z(1+w+w^2)).
(6)

The trinomial triangle gives the triangle of trinomial coefficients,

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
(7)

(OEIS A027907).

The central column of the trinomial triangle gives the central trinomial coefficients.

The trinomial coefficient also counts ordered n-tuples with entries from {-1,0,1} whose sum is k. For example, there are seven ordered triples whose sum is 0, (-1,0,1), (-1,1,0), (0,-1,1), (0,0,0), (0,1,-1), (1,-1,0), (1,0,-1), so (3; 0)_2=7.

An alternative (but different) definition of the trinomial coefficients is as the coefficients in (x+y+z)^n (Andrews 1990), which is therefore a multinomial coefficient with k=3, giving

(n_1,n_2,n_3)!=((n_1+n_2+n_3)!)/(n_1!n_2!n_3!).
(8)

Euler (1767) studied trinomial coefficients in his 20-page article "Observationes analyticae," written in 1763 and published in the volume bearing the year 1765.

The following table gives the first few columns of the trinomial triangle, starting with n=k in each row.

kOEIS(n,k)-trinomial coefficients
0A0024261, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, ...
1A0057171, 2, 6, 16, 45, 126, 357, 1016, 2907, 8350, ...
2A0145311, 3, 10, 30, 90, 266, 784, 2304, ...
3A0145321, 4, 15, 50, 161, 504, 1554, 4740, ...
4A0145331, 5, 21, 77, 266, 882, 2850, 9042, ...
5A0984701, 6, 28, 112, 414, 1452, 4917, ...

The diagonals (n; n-k)_2 are summarized in the following table.

k(n; n-k)_2OEIS
01
1nA000027
21/2n(n+1)A000217
31/6(n-1)n(n+4)A005581
41/(24)(n-1)n(n^2+7n-6)A005712
51/(120)(n-2)(n-1)n(n+1)(n+12)A000574
61/(720)(n-2)(n-1)n(n^3+18n^2+17n-120)A005714
71/(5040)(n-3)(n-2)(n-1)n(n^3+27n^2+116n-120)A005715
81/(40320)(n-3)(n-2)(n-1)n(n+1)(n+10)(n^2+23n-84)A005716

For n>=1, the trinomial coefficients satisfy an identity similar to that of the binomial coefficients, namely

(n; k)_2=(n-1; k-1)_2+(n-1; k)_2+(n-1; k+1)_2
(9)

(Andrews 1990).

Explicit formulas for (n; k)_2 are given by

(n; k)_2=sum_(j=max(0,-k))^(|_(n-k)/2_|)(n!)/(j!(j+k)!(n-2j-k)!)
(10)
(n; k)_2=sum_(j=0)^(n)(-1)^j(n; j)(2n-2j; n-k-j)
(11)

(Andrews 1990), where |_x_| is the floor function. The corresponding closed forms are

(n; k)_2=(n!)/((n-k)!)_2F^~_1(1/2(k-n),1/2(k-n+1);k+1;4)
(12)
=((2n)!)/((n-k)!(n+k)!)_2F_1(-k-n,k-n;1/2-n;1/4),
(13)

where _2F^~_1(a,b;c;z) is a regularized hypergeometric function and _2F_1(a,b;c;z) is a hypergeometric function.

For at least n<2000 and 0<=k<=n, (n; k)_2 is prime iff n=k+1 is prime (since in that case (n; k)_2=n) or (n,k)=(2,0), (3, 0), or (4, 0). It is apparently not known if this property holds for all n. However, the k=1 column is explicitly given by

(n; 1)_2=nM_(n-1),
(14)

where M_k is a Motzkin number, and so can only be prime for n=2.

Euler (1767) noted the near-identity of central trinomial coefficients

3(n+1; 0)_2-(n+2; 0)_2=F_n(F_n+1),
(15)

where F_n is a Fibonacci number, which holds only for n<=7 (Andrews 1990). For n=0, 1, ..., the first few values of the left side are 0, 2, 2, 6, 12, 30, 72, 182, 464, ... (OEIS A103872), while the values on the right side are 0, 2, 2, 6, 12, 30, 72, 182, 462, ... (OEIS A059727). This example was sent by D. Knuth to R. K. Guy, who included it in his article on the strong law of small numbers (Guy 1990, p. 18). Meanwhile, Guy had met G. Andrews at the Bateman retirement conference and showed it to him. Half an hour later, Andrews came back with the q-series identity from which Euler's near result follows (Guy 1990, p. 19). In particular, defining

E_n(a,b)=sum_(k=-infty)^infty[(n; 10k+a)_2-(n; 10k+b)_2]
(16)

gives the identities for n>=1,

E_n(1,2)=1/2F_n(F_n+1)
(17)
E_(n-1)(0,3)=1/2F_n(F_n+1)
(18)
E_(n+1)(0,1)=1/2F_n(F_n+1)
(19)
E_n(1,4)=F_(n+1)F_n
(20)
E_(n+1)(2,3)=F_(n+1)F_n
(21)
E_n(3,4)=1/2F_n(F_n-1)
(22)
E_(n-1)(2,5)=1/2F_n(F_n-1)
(23)
E_(n+1)(4,5)=1/2F_n(F_n-1)
(24)
E_n(1,3)=1/2(F_(2n)+F_n)
(25)
E_n(2,4)=1/2(F_(2n)-F_n)
(26)
E_n(1,5)=1/2(F_(2n+1)-F_(n-1))
(27)
E_n(0,4)=1/2(F_(2n+1)+F_(n-1))
(28)
E_n(0,2)=1/2(F_(2n-1)+F_(n+1))
(29)
E_n(3,5)=1/2(F_(2n-1)-F_(n+1))
(30)
E_n(0,5)=F_(2n-1)+F_nF_(n-1)
(31)

(Andrews 1990). This then leads to the near-identity via

3(n+1; 0)_2-(n+2; 0)_2=2(n+1; 0)_2-2(n+1; 1)_2
(32)
=2E_(n+1)(0,1) for n<=7
(33)
=F_n(F_n+1) for n<=7.
(34)

Andrews (1990) also gave the identities for n>=1

sum_(k=-infty)^infty(n; 10k+a)_2={1/2F_n^2+1/2F_(n-1)^2+1/2F_(n-1)F_n+2/5F_(n-1)+1/5F_n+1/(10)3^n for a=0; 1/2F_(n-1)F_n+1/2F_n^2-1/(10)F_(n-1)+1/5F_n+1/(10)3^n for a=1; 1/2F_(n-1)F_n-1/(10)F_(n-1)-3/(10)F_n+1/(10)3^n for a=2; -1/2F_(n-1)F_n-1/(10)F_(n-1)-3/(10)F_n+1/(10)3^n for a=3; -1/2F_(n-1)F_n-1/2F_n^2-1/(10)F_(n-1)+1/5F_n+1/(10)3^n for a=4; -1/2F_(n-1)^2-1/2F_(n-1)F_n-1/2F_n^2+2/5F_(n-1)+1/5F_n+1/(10)3^n for a=5.
(35)

See also

Binomial Coefficient, Central Trinomial Coefficient, Motzkin Number, Multinomial Coefficient, Trinomial, Trinomial Triangle

Explore with Wolfram|Alpha

References

Andrews, G. E. "Euler's 'exemplum memorabile inductionis fallacis' and q-Trinomial Coefficients." J. Amer. Math. Soc. 3, 653-669, 1990. https://doi.org/10.1090/S0894-0347-1990-1040390-4.Andrews, G. and Baxter, R. J. "Lattice Gas Generalization of the Hard Hexagon Model. III. q-Trinomial Coefficients." J. Stat. Phys. 47, 297-330, 1987.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 78, 1974.Euler, L. "Observationes analyticae." Novi Commentarii Academiae Scientiarum Petropolitanae 11, 124-143, 1767. Reprinted in Opera Omnia, Series Prima, Vol. 15 (Ed. G. Faber). Leipzig and Berlin, Germany: Teubner, pp. 50-69, 1927. https://scholarlycommons.pacific.edu/euler-works/326/.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. Reading, MA: Addison-Wesley, p. 575, 1990.Guy, R. K. "The Second Strong Law of Small Numbers." Math. Mag. 63, 3-20, 1990.Henrici, P. Applied and Computational Complex Analysis, Vol. 1: Power Series-Integration-Conformal Mapping-Location of Zeros. New York: Wiley, p. 42, 1988.Hoggatt, V. E. Jr., and Bicknell, M. "Diagonal Sums of Generalized Pascal Triangles." Fib. Quart. 7, 341-358 and 393, 1969.Riordan, J. Combinatorial Identities. New York: Wiley, p. 74, 1979.Shapiro, L. W.; Getu, S.; Woan, W.-J.; and Woodson, L. C. "The Riordan Group." Disc. Appl. Math. 34, 229-239, 1991.Sloane, N. J. A. Sequences A000027, A000217, A000574, A002426/M2673, A005581, A005712, A005714, A005715, A005716, A005717/M1612, A014531, A014532, A014533, A027907, A059727, A098470, and A103872 in "The On-Line Encyclopedia of Integer Sequences."Warnaar, S. O. "q-Trinomial Identities." 5 Oct 1998. https://arxiv.org/abs/math/9810018.

Referenced on Wolfram|Alpha

Trinomial Coefficient

Cite this as:

Weisstein, Eric W. "Trinomial Coefficient." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TrinomialCoefficient.html

Subject classifications