Jump to content

Trinomial triangle

From Wikipedia, the free 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:

The -th entry of the -th row is denoted by

.

Rows are counted starting from 0. The entries of the -th row are indexed starting with from the left, and the middle entry has index 0. The symmetry of the entries of a row about the middle entry is expressed by the relationship

Properties

[edit]

The -th row corresponds to the coefficients in the polynomial expansion of the expansion of the trinomial raised to the -th power:[1]

or, symmetrically,

,

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

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

The sum of the elements of -th row is .

Recurrence formula

[edit]

The trinomial coefficients can be generated using the following recurrence formula:[1]

,
for ,

where for and .

Central trinomial coefficients

[edit]

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 -th central trinomial coefficient is given by

Their generating function is[2]

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

for ,

where is the n-th Fibonacci number. For larger , however, this relationship is incorrect. George Andrews explained this fallacy using the general identity[3]

Applications

[edit]

In chess

[edit]
a7 oneb7 threec7 sixd7 sevene7 sixf7 threeg7 one
a6 threeb6 onec6 twod6 threee6 twof6 oneg6 three
a5 sixb5 twoc5 oned5 onee5 onef5 twog5 six
a4 sevenb4 threec4 oned4 white kinge4 onef4 threeg4 seven
a3 sixb3 twoc3 oned3 onee3 onef3 twog3 six
a2 threeb2 onec2 twod2 threee2 twof2 oneg2 three
a1 oneb1 threec1 sixd1 sevene1 sixf1 threeg1 one
Number of ways to reach a cell with the minimum number of moves

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

[edit]

The coefficient of in the expansion of gives the number of different ways to draw cards from two identical sets of playing cards each.[4] 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,

.

In particular, this provides the formula 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 pairs of identical cards from the two sets, which is the binomial coefficient . The remaining cards can then be chosen in ways,[4] which can be written in terms of the binomial coefficients as

.

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

[edit]
  1. ^ a b Weisstein, Eric W. "Trinomial Coefficient". MathWorld.
  2. ^ Weisstein, Eric W. "Central Trinomial Coefficient". MathWorld.
  3. ^ George Andrews, Three Aspects for Partitions. Séminaire Lotharingien de Combinatoire, B25f (1990) Online copy
  4. ^ a b Andreas Stiller: Pärchenmathematik. Trinomiale und Doppelkopf. ("Pair mathematics. Trinomials and the game of Doppelkopf"). c't Issue 10/2005, p. 181ff

Further reading

[edit]