Divine coincidence

2013-12-28T12:12:35Z

81.236.236.128:

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:

<center>
<math>\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}</math>
</center>

The <math>k</math>-th entry of the <math>n</math>-th row is denoted by

: <math>{n\choose k}_2</math>.

Rows are counted starting from 0. The entries of the <math>n</math>-th row are indexed starting with <math>-n</math> 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

: <math>{n\choose k}_2={n\choose-k}_2</math>

== Properties ==

The <math>n</math>-th row corresponds to the coefficients in the [[polynomial expansion]] of the expansion of the [[trinomial]] <math>(1 + x + x^2)</math> raised to the <math>n</math>-th power:<ref name="MathWorldTrinomialCoefficient">{{MathWorld|TrinomialCoefficient|Trinominal Coefficient}}</ref>

:<math>\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}</math>

or, symmetrically,
:<math>\left(1+x+1/x\right)^n=\sum_{k=-n}^{n}{n\choose k}_2 x^k</math>,
hence the alternative name '''trinomial coefficients''' because of their relationship to the [[multinomial coefficients]]:

: <math>{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)!}</math>

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

The sum of the elements of <math>n</math>-th row is <math>3^n</math>.

== Recursion formula ==

The trinomial coefficients can be generated using the following [[Recursion|recursion formula]]:<ref name="MathWorldTrinomialCoefficient"/>

:<math>{0\choose 0}_2=1</math>,

:<math>{n+1\choose k}_2={n\choose k-1}_2+{n\choose k}_2+{n\choose k+1}_2</math> for <math>n\geq 0</math>,

where <math>{n\choose k}_2=0</math> for <math>\ k<-n</math> and <math>\ k>n</math>.

== The middle entries ==

The middle entries of the trinomial triangle {{OEIS|A002426}}

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

were studied by [[Leonhard Euler|Euler]]. The middle entry for the <math>n</math>-th row is given by

: <math>{n\choose0}_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}.</math>

The corresponding [[generating function]] is<ref>{{MathWorld|CentralTrinomialCoefficient|Central Trinomial Coefficient}}</ref>

: <math>1+x+3x^2+7x^3+19x^4+\ldots=\frac1{\sqrt{(1+x)(1-3x)}}.</math>

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

: <math>3{n+1\choose0}_2-{n+2\choose0}_2=f_n(f_n+1)</math> for <math>0\leq n\leq 7</math>

where <math>f_n</math> stands for the [[Fibonacci sequence]]. For larger <math>n</math>, however, this relationship is incorrect. [[George Andrews (mathematician)|George Andrews]] explained this fallacy using the general identity<ref>George Andrews, Three Aspects for Partitions. ''Séminaire Lotharingien de Combinatoire'', B25f (1990) [http://www.mat.univie.ac.at/~slc/opapers/s25andrews.html Online copy]</ref>

: <math>2\sum_{k\in\mathbb Z}\left[{n+1\choose 10k}_2-{n+1\choose 10k+1}_2\right]=f_n(f_n+1).</math>

== Chess mathematics ==

[[File:King walks.svg|thumb|right|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 (chess)|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.

<br style="clear:both;" />

== Importance in combinatorics ==
The coefficient of <math>x^k</math> in the polynomial expansion of <math>\left(1+x+x^2\right)^n</math> specifies the number of different ways of randomly drawing <math>k</math> cards from two sets of <math>n</math> identical playing cards.<ref name="ct200510">Andreas Stiller: ''Pärchenmathematik. Trinomiale und Doppelkopf.'' ("Pair mathematics. Trinomials and the game of ''Doppelkopf''"). [[c't]] Heft 10/2005, p. 181ff</ref> For example, in such a card game with two sets of the three cards A, B, C, the choices look like this:

{| class="prettytable"
!bgcolor=ececec|Number of selected cards
!bgcolor=ececec|Number of options
!bgcolor=ececec|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
|}

In particular, this results in <math>{24\choose 12-24}_2={24\choose -12}_2={24\choose 12}_2</math> 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 <math>p</math> pairs of identical cards from the two sets, which is <math>{n\choose p}</math>. The remaining <math>k-2p</math> cards can then be chosen in <math>{n-p\choose k-2p}</math> ways,<ref name="ct200510"/> which can be written in terms of the [[binomial coefficients]] as

:<math>{n\choose k-n}_2=\sum_{p=\max(0,k-n)}^{\min(n,[k/2])}{n\choose p}{n-p \choose k-2p}</math>.

For example,

:<math>6={3\choose 2-3}_2={3\choose 0}{3\choose 2}+{3\choose 1}{2\choose 0}=1\cdot 3+3\cdot 1</math>.

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 ==
{{reflist}}

== Further reading ==

* [[Leonhard Euler]], ''Observationes analyticae'' ("Analytical observations"). ''Novi Commentarii academiae scientiarum Petropolitanae'' 11 (1767) 124–143 [http://www.math.dartmouth.edu/~euler/pages/E326.html PDF]

[[Category:Discrete mathematics]]
[[Category:Triangles of numbers]]
[[Category:Factorial and binomial topics]]

formulasearchengine - User contributions [en]

Divine coincidence