Quelltext der Seite Trinomial Triangle

Das '''Trinomial Triangle''' ({{enS}}, etwa ''Trinomiales Dreieck'') ist eine Abwandlung zum [[Pascalsches Dreieck|Pascalschen Dreieck]]. Der Unterschied besteht darin, dass ein Eintrag die Summe der ''drei'' (statt wie im originalen Pascalschen Dreieck der ''zwei'') darüberstehenden Einträge ist. Bisher hat sich wegen der geringen mathematischen Relevanz kein allgemein anerkannter deutscher Begriff durchsetzen können; ein Beispiel für einen praktisch verwendeten Begriff ist „Pascalsches 3-arithmetisches Dreieck“.<ref>Jewgeni Gik: ''Schach und Mathematik''. Reinhard Becker Verlag, 1986, ISBN 3-930640-37-6, Seite 79</ref>
<div class="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>
</div>
Für den <math>k</math>-ten Eintrag in der <math>n</math>-ten Zeile hat sich die Bezeichnung
: <math>{n\choose k}_2</math>
etabliert. Die Zeilen werden dabei mit <math>n=0</math> beginnend gezählt, die Einträge in der <math>n</math>-ten Zeile mit <math>k = -n</math> beginnend bis <math>k=n</math>. Der mittlere Eintrag hat also Index <math>k=0</math>, und die Symmetrie wird durch die Formel
: <math>{n\choose k}_2={n\choose-k}_2</math>
ausgedrückt.

== Eigenschaften ==
Die <math>n</math>-te Zeile entspricht den Koeffizienten der [[Polynom]]entwicklung der <math>n</math>-ten Potenz von <math>1 + x + x^2</math>, also eines speziellen [[Trinom]]s:<ref name="MathWorldTrinomialCoefficient">{{MathWorld|id=TrinomialCoefficient|title=Trinomial 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>

oder symmetrisch
:<math>\left(1+x+1/x\right)^n=\sum_{k=-n}^{n}{n\choose k}_2 x^k</math>.

Daraus ergibt sich auch die Bezeichnung '''Trinomialkoeffizienten''' und die Beziehung zu den [[Multinomialkoeffizient]]en:
: <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>

Des Weiteren sind interessante Folgen in den Diagonalen enthalten, etwa die [[Dreieckszahl]]en.

Die Summe der Elemente der <math>n</math>-ten Zeile ist <math>\sum_{k=-n}^n {n\choose k}_2 = 3^n</math>.

Die alternierende Summe jeder Zeile ergibt Eins: <math>\sum_{k=-n}^n (-1)^{n+k}{n\choose k}_2 = 1</math>.

Formal folgen beide Formeln aus der ersten Formel für ''x=1'' und ''x=-1''.

== Rekursionsformel ==
Die Trinomialkoeffizienten lassen sich mit folgender [[Rekursion]]sformel berechnen:<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> für <math>n\geq 0</math>,
wobei <math>{n\choose k}_2=0</math> für <math>\ k<-n</math> und <math>\ k>n</math> zu setzen ist.
== Die mittleren Einträge ==

Die Folge der mittleren Einträge ({{OEIS|A002426}})
: 1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, …
wurde bereits von [[Leonhard Euler|Euler]] untersucht: Sie ist explizit gegeben durch
: <math>{n\choose0}_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}.</math>
Die zugehörige [[erzeugende Funktion]] ist
: <math>1+x+3x^2+7x^3+19x^4+\ldots=\frac1{\sqrt{(1+x)(1-3x)}}.</math><ref>{{MathWorld|id=CentralTrinomialCoefficient|title=Central Trinomial Coefficient}}</ref>
Euler bemerkte auch das ''exemplum memorabile inductionis fallacis'' (bemerkenswertes Beispiel trügerischer Induktion):
: <math>3{n+1\choose0}_2-{n+2\choose0}_2=f_n(f_n+1)</math> für <math>0\leq n\leq 7</math>
mit der [[Fibonacci-Folge]] <math>(f_n)</math>. Für größere <math>n</math> ist die Beziehung jedoch falsch. [[George Andrews (Mathematiker)|George Andrews]] erklärte dies durch die allgemeingültige Identität.<ref>George Andrews, Three Aspects for Partitions. ''Séminaire Lotharingien de Combinatoire'', B25f (1990) http://www.mat.univie.ac.at/~slc/opapers/s25andrews.html</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>

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

== Bedeutung in der Kombinatorik ==

=== Kartenspiele ===
In der [[Kombinatorik]] gibt der Koeffizient von <math>x^k</math> in der Polynomentwicklung von <math>\left(1+x+x^2\right)^n</math> an, wie viele verschiedene Möglichkeiten es gibt, um ungeordnet <math>k</math> Karten aus einem Paket von zwei identischen Kartenspielen je <math>n</math> unterschiedlicher Karten auszuwählen.<ref name="ct200510">Andreas Stiller: ''Pärchenmathematik. Trinomiale und Doppelkopf.'' [[c’t]] Heft 10/2005, S.&nbsp;181ff.</ref> Hat man beispielsweise zwei Kartenspiele mit den Karten A,B,C, so sieht das folgendermaßen aus:

{| class="wikitable"
|-
! Anzahl gewählte Karten
! Anzahl Möglichkeiten
! Möglichkeiten
|-
|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
|}

Insbesondere ergibt sich daraus <math>{24\choose 12-24}_2={24\choose -12}_2={24\choose 12}_2=287.134.346</math><ref>[https://coursera.cs.princeton.edu/introcs/assignments/recursion/specification.php Trinomial Triangle als Programmierbeispiel]</ref> (also gut 287 Millionen) für die Anzahl der unterschiedlichen Hände im [[Doppelkopf]].

Alternativ lässt sich die Zahl dieser Möglichkeit auch berechnen, indem man über die Anzahl <math>p</math> der Pärchen in der Hand aufsummiert; dafür gibt es <math>{n\choose p}</math> Möglichkeiten und für die verbleibenden <math>k-2p</math> Karten gibt es <math>{n-p\choose k-2p}</math> Möglichkeiten<ref name="ct200510" />, sodass sich daraus folgende Beziehung zu den [[Binomialkoeffizient]]en ergibt:

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

Beispielsweise gilt

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

In obigem Beispiel entspricht das dann für die Auswahl von 2 Karten den 3 Möglichkeiten mit 0 Pärchen (AB, AC, BC) sowie den 3 Möglichkeiten mit einem Pärchen (AA, BB, CC).

=== Schachmathematik ===
[[Datei:King walks.svg|mini|Anzahl der Möglichkeiten, ein Feld mit der minimalen Zahl von Zügen zu erreichen]]
<math>{n\choose k}_2</math> entspricht auch der Zahl der möglichen Pfade eines [[König (Schach)|Schachkönigs]], um in minimaler Zahl von Zügen ein Feld des Schachbretts zu erreichen, das von seinem aktuellen Aufenthaltsort <math>(n, k)</math> Felder entfernt ist.

Dies gilt nur unter der Bedingung, dass die möglichen Pfade nicht durch den Brettrand eingeschränkt sind.

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

== Einzelnachweise ==
<references />

[[Kategorie:Diskrete Mathematik]]