Trinomial Triangle

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Trinomial Triangle (engl., etwa Trinomiales Dreieck) ist eine Abwandlung zum Pascalschen Dreieck. Der Unterschied besteht darin, dass ein Eintrag die Summe der drei (statt wie im echten Pascalschen Dreieck der zwei) darüberstehenden Einträge ist. Bisher hat sich wegen der eher geringen mathematischen Relevanz kein allgemein anerkannter deutscher Begriff durchsetzen können; eine Beispiel für einen praktisch verwendeten Begriff ist „Pascalsches 3-arithmetisches Dreieck“.[1]

\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}

Für den k-ten Eintrag in der n-ten Zeile hat sich die Bezeichnung

{n\choose k}_2

etabliert. Die Zeilen werden dabei mit n=0 beginnend gezählt, die Einträge in der n-ten Zeile mit k = -n beginnend bis k=n. Der mittlere Eintrag hat also Index k=0, und die Symmetrie wird durch die Formel

{n\choose k}_2={n\choose-k}_2

ausgedrückt.

Eigenschaften[Bearbeiten]

Die n-te Zeile entspricht den Koeffizienten der Polynomentwicklung der n-ten Potenz von 1 + x + x^2, also eines speziellen Trinoms[2]:

\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}

oder symmetrisch

\left(1+x+1/x\right)^n=\sum_{k=-n}^{n}{n\choose k}_2 x^k.

Daraus ergibt sich auch die Bezeichnung Trinomialkoeffizienten und die Beziehung zu den Multinomialkoeffizienten:

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

Des Weiteren sind interessante Folgen in den Diagonalen enthalten, etwa die Dreieckszahlen.

Die Summe der Elemente der n-ten Zeile ist 3^n.

Rekursionsformel[Bearbeiten]

Die Trinomialkoeffizienten lassen sich mit folgender Rekursionsformel berechnen[2]:

{0\choose 0}_2=1,
{n+1\choose k}_2={n\choose k-1}_2+{n\choose k}_2+{n\choose k+1}_2 für n\geq 0,

wobei {n\choose k}_2=0 für \ k<-n und \ k>n zu setzen ist.

Die mittleren Einträge[Bearbeiten]

Die Folge der mittleren Einträge (Folge A002426 in OEIS)

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

wurde bereits von Euler untersucht: Sie ist explizit gegeben durch

{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}.

Die zugehörige erzeugende Funktion ist

1+x+3x^2+7x^3+19x^4+\ldots=\frac1{\sqrt{(1+x)(1-3x)}}.[3]

Euler bemerkte auch das exemplum memorabile inductionis fallacis (bemerkenswertes Beispiel trügerischer Induktion):

3{n+1\choose0}_2-{n+2\choose0}_2=f_n(f_n+1) für 0\leq n\leq 7

mit der Fibonacci-Folge (f_n). Für größere n ist die Beziehung jedoch falsch. George Andrews erklärte dies durch die allgemeingültige Identität[4]

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

Schachmathematik[Bearbeiten]

Anzahl der Möglichkeiten, ein Feld mit der minimalen Zahl von Zügen zu erreichen

Das Dreieck entspricht der Zahl der möglichen Pfade eines Schachkönigs, um in minimaler Zahl von Zügen das jeweilige Feld des Rasters zu erreichen (sofern er dabei nicht durch den Brettrand eingeschränkt wird).

Bedeutung in der Kombinatorik[Bearbeiten]

Siehe auch: Kombinatorik

Der Koeffizient von x^k in der Polynomentwicklung von \left(1+x+x^2\right)^n gibt an, wie viele verschiedene Möglichkeiten es gibt, um ungeordnet k Karten aus einem Paket von zwei identischen Kartenspielen je n unterschiedlicher Karten auszuwählen.[5] Hat man beispielsweise zwei Kartenspiele mit den Karten A,B,C, so sieht das folgendermaßen aus:

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 {24\choose 12-24}_2={24\choose -12}_2={24\choose 12}_2 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 p der Pärchen in der Hand aufsummiert; dafür gibt es {n\choose p} Möglichkeiten und für die verbleibenden k-2p Karten gibt es {n-p\choose k-2p} Möglichkeiten[5], sodass sich daraus folgende Beziehung zu den Binomialkoeffizienten ergibt:

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

Beispielsweise gilt

6={3\choose 2-3}_2={3\choose 0}{3\choose 2}+{3\choose 1}{2\choose 0}=1\cdot 3+3\cdot 1.

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

Literatur[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  1. Jewgeni Gik: Schach und Mathematik. Reinhard Becker Verlag, 1986, ISBN 3930640376, Seite 79
  2. a b Eric W. Weisstein: Trinomial Coefficient. In: MathWorld (englisch).
  3. Eric W. Weisstein: Central Trinomial Coefficient. In: MathWorld (englisch).
  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. Trinomiale und Doppelkopf. c't Heft 10/2005, S 181ff