• Images
• Videos
• Documents
• Books
• Articles

Properties

The n {\displaystyle n} -th row corresponds to the coefficients in the polynomial expansion of the expansion of the trinomial ( 1 + x + x 2 ) {\displaystyle (1+x+x^{2})} raised to the n {\displaystyle n} -th power:¹

( 1 + x + x 2 ) n = ∑ j = 0 2 n ( n j − n ) 2 x j = ∑ k = − n n ( n k ) 2 x n + k {\displaystyle \left(1+x+x^{2}\right)^{n}=\sum _{j=0}^{2n}{n \choose j-n}_{2}x^{j}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{n+k}}

or, symmetrically,

( 1 + x + 1 / x ) n = ∑ k = − n n ( n k ) 2 x k {\displaystyle \left(1+x+1/x\right)^{n}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{k}} ,

hence the alternative name trinomial coefficients because of their relationship to the multinomial coefficients:

( n k ) 2 = ∑ 0 ≤ μ , ν ≤ n μ + 2 ν = n + k n ! μ ! ν ! ( n − μ − ν ) ! {\displaystyle {n \choose k}_{2}=\sum _{\textstyle {0\leq \mu ,\nu \leq n \atop \mu +2\nu =n+k}}{\frac {n!}{\mu !\,\nu !\,(n-\mu -\nu )!}}}

Furthermore, the diagonals have interesting properties, such as their relationship to the triangular numbers.

The sum of the elements of n {\displaystyle n} -th row is 3 n {\displaystyle 3^{n}} .

Recurrence formula

The trinomial coefficients can be generated using the following recurrence formula:²

( 0 0 ) 2 = 1 {\displaystyle {0 \choose 0}_{2}=1} , ( n + 1 k ) 2 = ( n k − 1 ) 2 + ( n k ) 2 + ( n k + 1 ) 2 {\displaystyle {n+1 \choose k}_{2}={n \choose k-1}_{2}+{n \choose k}_{2}+{n \choose k+1}_{2}} for n ≥ 0 {\displaystyle n\geq 0} ,

where ( n k ) 2 = 0 {\displaystyle {n \choose k}_{2}=0} for   k < − n {\displaystyle \ k<-n} and   k > n {\displaystyle \ k>n} .

Central trinomial coefficients

The middle entries of the trinomial triangle

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, … (sequence A002426 in the OEIS)

were studied by Euler and are known as central trinomial coefficients.

The only known prime central trinomial coefficients are 3, 7 and 19 at n = 2, 3 and 4.

The n {\displaystyle n} -th central trinomial coefficient is given by

( n 0 ) 2 = ∑ k = 0 n n ( n − 1 ) ⋯ ( n − 2 k + 1 ) ( k ! ) 2 = ∑ k = 0 n ( n 2 k ) ( 2 k k ) . {\displaystyle {n \choose 0}_{2}=\sum _{k=0}^{n}{\frac {n(n-1)\cdots (n-2k+1)}{(k!)^{2}}}=\sum _{k=0}^{n}{n \choose 2k}{2k \choose k}.}

Their generating function is³

1 + x + 3 x 2 + 7 x 3 + 19 x 4 + … = 1 ( 1 + x ) ( 1 − 3 x ) . {\displaystyle 1+x+3x^{2}+7x^{3}+19x^{4}+\ldots ={\frac {1}{\sqrt {(1+x)(1-3x)}}}.}

Euler noted the following exemplum memorabile inductionis fallacis ("notable example of fallacious induction"):

3 ( n + 1 0 ) 2 − ( n + 2 0 ) 2 = F n ( F n + 1 ) {\displaystyle 3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=F_{n}(F_{n}+1)} for 0 ≤ n ≤ 7 {\displaystyle 0\leq n\leq 7} ,

where F n {\displaystyle F_{n}} is the n-th Fibonacci number. For larger n {\displaystyle n} , however, this relationship is incorrect. George Andrews explained this fallacy using the general identity⁴

2 ∑ k ∈ Z [ ( n + 1 10 k ) 2 − ( n + 1 10 k + 1 ) 2 ] = F n ( F n + 1 ) . {\displaystyle 2\sum _{k\in \mathbb {Z} }\left[{n+1 \choose 10k}_{2}-{n+1 \choose 10k+1}_{2}\right]=F_{n}(F_{n}+1).}

Applications

In chess

The triangle corresponds to the number of possible paths that can be taken by the king in a game of chess. The entry in a cell represents the number of different paths (using a minimum number of moves) the king can take to reach the cell.

In combinatorics

The coefficient of x k {\displaystyle x^{k}} in the expansion of ( 1 + x + x 2 ) n {\displaystyle \left(1+x+x^{2}\right)^{n}} gives the number of different ways to draw k {\displaystyle k} cards from two identical sets of n {\displaystyle n} playing cards each.⁵ For example, from two sets of the three cards A, B, C, the different drawings are:

Number of selected cards	Number of options	Options
0	1
1	3	A, B, C
2	6	AA, AB, AC, BB, BC, CC
3	7	AAB, AAC, ABB, ABC, ACC, BBC, BCC
4	6	AABB, AABC, AACC, ABBC, ABCC, BBCC
5	3	AABBC, AABCC, ABBCC
6	1	AABBCC

For example,

6 = ( 3 2 − 3 ) 2 = ( 3 0 ) ( 3 2 ) + ( 3 1 ) ( 2 0 ) = 1 ⋅ 3 + 3 ⋅ 1 {\displaystyle 6={3 \choose 2-3}_{2}={3 \choose 0}{3 \choose 2}+{3 \choose 1}{2 \choose 0}=1\cdot 3+3\cdot 1} .

In particular, this provides the formula ( 24 12 − 24 ) 2 = ( 24 − 12 ) 2 = ( 24 12 ) 2 {\displaystyle {24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}} for the number of different hands in the card game Doppelkopf.

Alternatively, it is also possible to arrive at this expression by considering the number of ways of choosing p {\displaystyle p} pairs of identical cards from the two sets, which is the binomial coefficient ( n p ) {\displaystyle {n \choose p}} . The remaining k − 2 p {\displaystyle k-2p} cards can then be chosen in ( n − p k − 2 p ) {\displaystyle {n-p \choose k-2p}} ways,⁶ which can be written in terms of the binomial coefficients as

( n k − n ) 2 = ∑ p = max ( 0 , k − n ) min ( n , [ k / 2 ] ) ( n p ) ( n − p k − 2 p ) {\displaystyle {n \choose k-n}_{2}=\sum _{p=\max(0,k-n)}^{\min(n,[k/2])}{n \choose p}{n-p \choose k-2p}} .

The example above corresponds to the three ways of selecting two cards without pairs of identical cards (AB, AC, BC) and the three ways of selecting a pair of identical cards (AA, BB, CC).

Further reading

• Leonhard Euler (1767). "Observationes analyticae ("Analytical observations")". Novi Commentarii Academiae Scientiarum Petropolitanae. 11: 124–143.

References

1. Weisstein, Eric W. "Trinomial Coefficient". MathWorld. /wiki/Eric_W._Weisstein ↩

2. Weisstein, Eric W. "Trinomial Coefficient". MathWorld. /wiki/Eric_W._Weisstein ↩

3. Weisstein, Eric W. "Central Trinomial Coefficient". MathWorld. /wiki/Eric_W._Weisstein ↩

4. George Andrews, Three Aspects for Partitions. Séminaire Lotharingien de Combinatoire, B25f (1990) Online copy https://www.mat.univie.ac.at/~slc/opapers/s25andrews.html ↩

5. Andreas Stiller: Pärchenmathematik. Trinomiale und Doppelkopf. ("Pair mathematics. Trinomials and the game of Doppelkopf"). c't Issue 10/2005, p. 181ff /wiki/C%27t ↩

6. Andreas Stiller: Pärchenmathematik. Trinomiale und Doppelkopf. ("Pair mathematics. Trinomials and the game of Doppelkopf"). c't Issue 10/2005, p. 181ff /wiki/C%27t ↩