Trinomial triangle - Alchetron, The Free Social Encyclopedia

The trinomial triangle is a variation of Pascal's triangle. The difference between the two is that an entry in the trinomial triangle is the sum of the three (rather than the two in Pascal's triangle) entries above it:

Properties

The n -th row corresponds to the coefficients in the polynomial expansion of the expansion of the trinomial ( 1 + x + x 2 ) raised to the 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

or, symmetrically,

( 1 + x + 1 / x ) n = ∑ k = − n n ( n 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 − μ − ν ) !

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

The sum of the elements of n -th row is 3 n .

Recursion formula

The trinomial coefficients can be generated using the following recursion formula:

( 0 0 ) 2 = 1 , ( n + 1 k ) 2 = ( n k − 1 ) 2 + ( n k ) 2 + ( n k + 1 ) 2 for n ≥ 0 ,

where ( n k ) 2 = 0 for k < − n and k > n .

The middle entries

The middle entries of the trinomial triangle (sequence A002426 in the OEIS)

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, …

were studied by Euler. The middle entry for the n -th row 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 ) .

The corresponding generating function is

1 + x + 3 x 2 + 7 x 3 + 19 x 4 + … = 1 ( 1 + x ) ( 1 − 3 x ) .

Euler also 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 ) for 0 ≤ n ≤ 7

where f n stands for the Fibonacci sequence. For larger 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 ) .

Chess mathematics

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.

Importance in combinatorics

The coefficient of x k in the polynomial expansion of ( 1 + x + x 2 ) n specifies the number of different ways of randomly drawing k cards from two sets of n identical playing cards. For example, in such a card game with two sets of the three cards A, B, C, the choices look like this:

In particular, this results in ( 24 12 − 24 ) 2 = ( 24 − 12 ) 2 = ( 24 12 ) 2 as the number of different hands in a game of Doppelkopf.

Alternatively, it is also possible to arrive at this number by considering the number of ways of choosing p pairs of identical cards from the two sets, which is ( n p ) . The remaining k − 2 p cards can then be chosen in ( n − p k − 2 p ) 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 ) .

For example,

6 = ( 3 2 − 3 ) 2 = ( 3 0 ) ( 3 2 ) + ( 3 1 ) ( 2 0 ) = 1 ⋅ 3 + 3 ⋅ 1 .

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

References

Trinomial triangle Wikipedia

(Text) CC BY-SA