Trinomial Triangle

The trinomial triangle ( English , about Trinomiales triangle ) is a modification to the Pascal's triangle . The difference is that an entry is the sum of the three (instead of the two entries in the original Pascal triangle ) above it. So far, due to its low mathematical relevance, no generally recognized German term has gained acceptance; an example of a term used in practice is “Pascal's 3-arithmetic triangle”.

${\displaystyle {\begin{matrix}&&&&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\end{matrix}}}$

The -th entry in the -th line has the name ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle {n \choose k}_{2}}$

established. The lines are counted starting with , the entries in the -th line starting with to . So the middle entry has index , and the symmetry is given by the formula ${\displaystyle n=0}$ ${\displaystyle n}$ ${\displaystyle k=-n}$ ${\displaystyle k=n}$ ${\displaystyle k=0}$

${\displaystyle {n \choose k}_{2}={n \choose -k}_{2}}$

expressed.

properties

The -th line corresponds to the coefficients of the polynomial expansion of the -th power of , i.e. a special trinomial : ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 1+x+x^{2}}$

${\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 symmetrical

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

This also gives the name trinomial coefficients and the relationship to the multinomial coefficients :

${\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 )!}}.}$

There are also interesting sequences in the diagonals, such as the triangular numbers .

The sum of the elements of the -th line is . ${\displaystyle n}$ ${\displaystyle \sum _{k=-n}^{n}{n \choose k}_{2}=3^{n}}$

The alternating sum of each line gives one: . ${\displaystyle \sum _{k=-n}^{n}(-1)^{n+k}{n \choose k}_{2}=1}$

Formally, both formulas follow from the first formula for x = 1 and x = -1 .

Recursion formula

The trinomial coefficients can be calculated with the following recursion formula:

${\displaystyle {0 \choose 0}_{2}=1}$,

${\displaystyle {n+1 \choose k}_{2}={n \choose k-1}_{2}+{n \choose k}_{2}+{n \choose k+1}_{2}}$for , ${\displaystyle n\geq 0}$

where for and is to be set. ${\displaystyle {n \choose k}_{2}=0}$ ${\displaystyle \ k<-n}$ ${\displaystyle \ k>n}$

The middle entries

The sequence of middle entries (sequence A002426 in OEIS )

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

has already been investigated by Euler : It is explicitly given by

${\displaystyle {n \choose 0}_{2}=\sum _{k=0}^{[n/2]}{\frac {n(n-1)\cdots (n-2k+1)}{(k!)^{2}}}=\sum _{k=0}^{[n/2]}{n \choose 2k}{2k \choose k}.}$

The corresponding generating function is

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

Euler also noted the exemplum memorabile inductionis fallacis (notable example of deceptive induction):

${\displaystyle 3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=f_{n}(f_{n}+1)}$ For ${\displaystyle 0\leq n\leq 7}$

with the Fibonacci sequence . For larger ones, however, the relationship is wrong. George Andrews explained this by the universal identity. ${\displaystyle (f_{n})}$ ${\displaystyle n}$

${\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).}$

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

meaning

Combinatorics

In combinatorics , the coefficient of in the polynomial expansion of indicates how many different possibilities there are to select random cards from a package of two identical decks of cards, each with different cards. For example, if you have two decks of cards with A, B, C, it looks like this: ${\displaystyle x^{k}}$ ${\displaystyle \left(1+x+x^{2}\right)^{n}}$ ${\displaystyle k}$ ${\displaystyle n}$

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

In particular, this results in the number of different hands in the double head . ${\displaystyle {24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}}$

Alternatively, the number of this possibility can also be calculated by adding up the number of pairs in the hand; There are possibilities for this and there are possibilities for the remaining cards , so that the following relationship to the binomial coefficients results: ${\displaystyle p}$ ${\displaystyle {n \choose p}}$ ${\displaystyle k-2p}$ ${\displaystyle {n-p \choose k-2p}}$

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

For example

6 = . ${\displaystyle {3 \choose 2-3}_{2}={3 \choose 0}{3 \choose 2}+{3 \choose 1}{2 \choose 0}=1\cdot 3+3\cdot 1}$

In the above example, for the selection of 2 cards, this corresponds to the 3 options with 0 pairs (AB, AC, BC) and the 3 options with one pair (AA, BB, CC).

Chess math

Number of ways to reach a field with the minimum number of moves

${\displaystyle {n \choose k}_{2}}$also corresponds to the number of possible paths a chess king can take to reach a space on the chessboard that is spaces away from its current location in a minimal number of moves . ${\displaystyle (n,k)}$

This only applies on condition that the possible paths are not restricted by the edge of the board.

literature

• Leonhard Euler , Observationes analyticae. Novi Commentarii academiae scientiarum Petropolitanae 11 (1767) 124-143 PDF

Individual evidence

1. ↑ Yevgeny Gik: Chess and Mathematics . Reinhard Becker Verlag, 1986, ISBN 3-930640-37-6 , page 79
2. ↑ ^{a b} Eric W. Weisstein : Trinomial Coefficient . In: MathWorld (English).
3. ↑ Eric W. Weisstein : Central Trinomial Coefficient . In: MathWorld (English).
4. ^ George Andrews, Three Aspects for Partitions. Séminaire Lotharingien de Combinatoire , B25f (1990) http://www.mat.univie.ac.at/~slc/opapers/s25andrews.html
5. ↑ ^{a b} Andreas Stiller: Pärchenmathematik. Trinomial and Doppelkopf. c't issue 10/2005, p. 181ff.