Trinomial Triangle

Grundidee und Schreibweise

Das Trinomial Triangle, etwa „Trinomiales Dreieck“, ist eine Abwandlung des Pascalschen Dreiecks. Während im Pascalschen Dreieck jeder Eintrag aus der Summe der zwei darüberstehenden Einträge entsteht, ist im Trinomial Triangle jeder Eintrag die Summe der drei darüberstehenden Einträge. Wegen der geringen mathematischen Relevanz gibt es keinen allgemein anerkannten deutschen Namen; ein praktisch verwendeter Begriff ist „Pascalsches 3-arithmetisches Dreieck“.

Für den k-ten Eintrag in der n-ten Zeile wird die Schreibweise {n \choose k}_2 verwendet. Die Zeilen werden bei n=0 begonnen. In der n-ten Zeile laufen die Einträge von k=-n bis k=n. Der mittlere Eintrag hat den Index k=0. Das Dreieck ist symmetrisch, was durch {n \choose k}_2={n \choose -k}_2 ausgedrückt wird.

Polynome und grundlegende Eigenschaften

Die n-te Zeile des Trinomial Triangle entspricht den Koeffizienten der Entwicklung der n-ten Potenz des Trinoms 1+x+x^2. Es gilt

(1+x+x^2)^n = \sum_{j=0}^{2n} {n \choose j-n}2 x^j = \sum{k=-n}^{n} {n \choose k}_2 x^{n+k}.

In symmetrischer Form lautet die Beziehung

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

Daher heißen die Einträge auch Trinomialkoeffizienten. Sie stehen in Beziehung zu den Multinomialkoeffizienten:

{n \choose k}2 = \sum{0\leq \mu,\nu\leq n,\ \mu+2\nu=n+k} \frac{n!}{\mu!,\nu!,(n-\mu-\nu)!}.

In den Diagonalen des Dreiecks treten interessante Folgen auf, zum Beispiel die Dreieckszahlen. Die Summe aller Elemente der n-ten Zeile ist

\sum_{k=-n}^{n} {n \choose k}_2 = 3^n.

Die alternierende Summe jeder Zeile ergibt 1:

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

Formal folgen diese beiden Formeln aus der Polynomformel durch Einsetzen von x=1 beziehungsweise x=-1.

Berechnung durch Rekursion

Die Trinomialkoeffizienten lassen sich rekursiv berechnen. Der Startwert ist

{0 \choose 0}_2=1.

Für n\geq 0 gilt

{n+1 \choose k}_2 = {n \choose k-1}_2 + {n \choose k}_2 + {n \choose k+1}_2.

Dabei setzt man {n \choose k}_2=0 für k<-n und für k>n. Diese Formel beschreibt genau die Konstruktionsregel des Dreiecks: Ein Eintrag entsteht aus der Summe der drei passenden Einträge der vorherigen Zeile.

Mittlere Einträge

Die mittleren Einträge sind die Einträge mit k=0. Ihre Folge beginnt

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

Sie ist als Folge A002426 in OEIS verzeichnet und wurde bereits von Euler untersucht. Explizit gilt

{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 erzeugende Funktion dieser Folge ist

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

Euler bemerkte außerdem ein „exemplum memorabile inductionis fallacis“, also ein bemerkenswertes Beispiel trügerischer Induktion:

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

wobei f_n die Fibonacci-Folge bezeichnet. Für größere n ist diese Beziehung jedoch falsch. George Andrews erklärte dies durch die allgemeingültige Identität

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

Kombinatorische Bedeutung bei Karten

In der Kombinatorik beschreibt der Koeffizient von x^k in (1+x+x^2)^n, wie viele Möglichkeiten es gibt, ungeordnet k Karten aus einem Paket von zwei identischen Kartenspielen mit jeweils n unterschiedlichen Karten auszuwählen. Bei zwei Kartenspielen mit den Karten A, B, C ergeben sich für 0 bis 6 gewählte Karten die Anzahlen 1, 3, 6, 7, 6, 3, 1. Für 2 Karten sind die Möglichkeiten AA, AB, AC, BB, BC, CC; für 3 Karten sind es AAB, AAC, ABB, ABC, ACC, BBC, BCC.

Für Doppelkopf ergibt sich daraus

{24 \choose 12-24}_2 = {24 \choose -12}_2 = {24 \choose 12}_2 = 287.134.346.

Das ist die Anzahl der unterschiedlichen Hände, also gut 287 Millionen.

Alternativ kann man die Anzahl über die Zahl p der Pärchen in der Hand berechnen. Für p Pärchen gibt es {n \choose p} Möglichkeiten; für die verbleibenden k-2p Karten gibt es {n-p \choose k-2p} Möglichkeiten. Dadurch erhält man die Beziehung

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

Beispiel: Für n=3 und k=2 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.

Das entspricht den 3 Möglichkeiten ohne Pärchen (AB, AC, BC) und den 3 Möglichkeiten mit einem Pärchen (AA, BB, CC).

Pfade eines Schachkönigs

Der Trinomialkoeffizient {n \choose k}_2 hat auch eine Bedeutung in der Schachmathematik. Er entspricht der Zahl der möglichen Pfade eines Schachkönigs, mit denen dieser in der minimalen Zahl von Zügen ein Feld erreichen kann, das von seinem aktuellen Aufenthaltsort (n,k) Felder entfernt ist.

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