Trinomial Triangle
aus Wikipedia, der freien Enzyklopädie
Das Trinomial Triangle ist ein Gegenstück zum Pascalschen Dreieck. Der Unterschied ist der, dass ein Eintrag die Summe der DREI darüberstehenden Einträge ist. Bisher hat sich wegen der eher geringen mathematischen Relevanz kein allgemein anerkannter deutscher Begriff durchsetzen können. In der deutschen Ausgabe des Buches „Schach und Mathematik“ von Jewgeni Gik wird es „Pascalsches 3-arithmetisches Dreieck“ genannt.
Für den k-ten Eintrag in der n-ten Zeile hat sich die Bezeichnung
etabliert. Die Zeilen werden dabei mit 0 beginnend gezählt, die Einträge in der n-ten Zeile mit − n beginnend, der mittlere Eintrag hat also Index 0, und die Symmetrie wird durch die Formel
ausgedrückt.
Inhaltsverzeichnis |
[Bearbeiten] Eigenschaften
Die n-te Zeile entspricht den Koeffizienten der Polynomentwicklung der n-ten Potenz von 1 + x + x2, also eines speziellen Trinoms[1]:
oder symmetrisch
- .
Daraus ergibt sich auch die Bezeichnung Trinomialkoeffizienten und die Beziehung zu den Polynomialkoeffizienten:
Weiters sind interessante Folgen in den Diagonalen enthalten, etwa die Dreieckszahlen.
[Bearbeiten] Rekursionsformel
Die Trinomialkoeffizienten lassen sich mit folgender Rekursionsformel berechnen[1]:
- ,
- für ,
- wobei für k < − n und k > n zu setzen ist.
[Bearbeiten] Die mittleren Einträge
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
Die zugehörige erzeugende Funktion ist
Euler bemerkte auch das exemplum memorabile inductionis fallacis(bemerkenswertes Beispiel trügerischer Induktion):
- für
mit der Fibonacci-Folge (fn). Für größere n ist die Beziehung jedoch falsch. George Andrews erklärte dies durch die allgemeingültige Identität[2]
[Bearbeiten] Schachmathematik
Das Dreieck entspricht der Zahl der möglichen Pfade eines Schachkönigs, die er (bei minimaler Anzahl von Zügen) nehmen kann, um vom obersten Feld des Rasters jenes mit der entsprechenden Zahl zu erreichen.
[Bearbeiten] Bedeutung in der Kombinatorik
Der Koeffizient von xk in der Polynomentwicklung von 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.[3] 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, AABBC |
6 | 1 | AABBCC |
Insbesondere ergibt sich daraus 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 Möglicheiten und für die verbleibenden k − 2p Karten gibt es Möglichkeiten[3], sodass sich daraus folgende Beziehung zu den Binomialkoeffizienten ergibt:
- .
Beispielsweise gilt
- 6=.
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).
[Bearbeiten] Literatur
- Leonhard Euler, Observationes analyticae. Novi Commentarii academiae scientiarum Petropolitanae 11 (1767) 124–143 PDF
[Bearbeiten] Einzelnachweise
- ↑ a b http://mathworld.wolfram.com/TrinomialCoefficient.html
- ↑ George Andrews, Three Aspects for Partitions. Séminaire Lotharingien de Combinatoire, B25f (1990) http://www.mat.univie.ac.at/~slc/opapers/s25andrews.html
- ↑ a b Andreas Stiller: Pärchenmathematik. Trinomiale und Doppelkopf. c't Heft 10/2005, S 181ff