Trinomial Triangle

Das Trinomial Triangle (englisch, etwa Trinomiales Dreieck) ist eine Abwandlung zum 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“.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}}

Für den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -ten Eintrag in der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Zeile hat sich die Bezeichnung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {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

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

$\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 $\sum _{k=-n}^{n}{n \choose k}_{2}=3^{n}$.

Die alternierende Summe jeder Zeile ergibt Eins: $\sum _{k=-n}^{n}(-1)^{n+k}{n \choose k}_{2}=1$.

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

Rekursionsformel

Die Trinomialkoeffizienten lassen sich mit folgender Rekursionsformel berechnen:

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

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

Die zugehörige erzeugende Funktion ist

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

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

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=f_{n}(f_{n}+1)} für $0\leq n\leq 7$

mit der Fibonacci-Folge $(f_{n})$. Für größere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ist die Beziehung jedoch falsch. George Andrews erklärte dies durch die allgemeingültige Identität.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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).}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {n\choose k-n}_2=\sum_{p=\max(0,k-n)}^{\min(n,[k/2])}{n\choose p}{n-p \choose k-2p}} .

Bedeutung in der Kombinatorik

Kartenspiele

In der Kombinatorik gibt der Koeffizient von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^k} in der Polynomentwicklung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(1+x+x^2\right)^n} an, wie viele verschiedene Möglichkeiten es gibt, um ungeordnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Karten aus einem Paket von zwei identischen Kartenspielen je Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} unterschiedlicher Karten auszuwählen. 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}=287.134.346} (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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} der Pärchen in der Hand aufsummiert; dafür gibt es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {n\choose p}} Möglichkeiten und für die verbleibenden Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k-2p} Karten gibt es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {n-p\choose k-2p}} Möglichkeiten, sodass sich daraus folgende Beziehung zu den Binomialkoeffizienten ergibt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {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=Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 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

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

${n \choose k}_{2}$ entspricht auch der Zahl der möglichen Pfade eines Schachkönigs, um in minimaler Zahl von Zügen ein Feld des Schachbretts zu erreichen, das von seinem aktuellen Aufenthaltsort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n, k)} 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 PDF