Einführung in $q$-Binomialkoeffizienten

Unterräume zählen

Sei $V$ ein endlich-dimensionaler Vektorraum über einem endlichen Körper $\IF$. Dann ist die zugrunde liegende Menge von $V$ eine endliche Menge. Insbesondere kann man sich die Frage stellen, wieviele Unterräume $V$ eigentlich genau besitzt. Die Antwort wird sicherlich von der Dimension $n$ von $V$ abhängen. Richten wir unser Augenmerk außerdem zunächst auf Unterräume einer festen Dimension $k$. Die Anzahl der Elemente von $\IF$ bezeichnen wir mit $q$. Man weiß, dass ein endlicher Körper mit $q$ Elementen genau dann existiert, wenn $q$ eine Primzahlpotenz ist, und dass dann je zwei solche Körper zueinander isomorph sind. Jeden solchen Körper bezeichnet man mit $\IF_q$. Wir werden das hier gar nicht brauchen, aber es ist nützlich zu wissen. Wir definieren für $n,k \in \IN$ den $q$-Binomialkoeffizienten $\smash{\binom{n}{k}_q}$ als die Anzahl der $k$-dimensionalen Unterräume eines $n$-dimensionalen $\IF_q$-Vektorraumes. Hier muss also $q$ eine Primzahlpotenz sein, aber wir werden später eine allgemeinere Definition sehen. Weil je zwei $n$-dimensionale Vektorräume zueinander isomorph sind, ist diese Anzahl wohldefiniert. Die Notation ist hier angelehnt an den Binomialkoeffizienten $\binom{n}{k}$, welcher völlig analog die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge bezeichnet. Wir lassen uns bei dieser Definition explizit die Freiheit, auch Vektorräume zuzulassen, die nicht die Form $\IF_q^n$ haben (genauso wie es beim Binomialkoeffizienten wichtig ist, nicht nur Mengen der Form $\{1,\dotsc,n\}$ zu betrachten). Die Anzahl aller Unterräume eines $n$-dimensionalen $\IF_q$-Vektorraumes ist $\smash{\sum_{k=0}^{n} \binom{n}{k}_q}$. Für $k > n$ gilt natürlich $\smash{\binom{n}{k}_q = 0}$. Wir dürfen uns bei der Berechnung also auf die Fälle $0 \leq k \leq n$ beschränken. Die Grenzfälle sind dabei einfach zu verstehen: Offensichtlich gilt $\displaystyle \binom{n}{0}_q = 1,\quad \binom{n}{n}_q = 1.$ Berechnen wir einmal $\smash{\binom{n}{1}_q}$. Sei dazu $V$ ein $n$-dimensionaler $\IF_q$-Vektorraum. Ein $1$-dimensionaler Unterraum von $V$ hat die Form $\langle v \rangle$ mit einem Vektor $v \in V \setminus \{0\}$. Für $v$ gibt es $q^n-1$ Möglichkeiten. Aber verschiedene Vektoren können denselben Unterraum erzeugen. Genauer gesagt sind die Erzeuger von $\langle v \rangle$ gegeben durch die $\lambda v$ mit $ \lambda \in \IF_q^{\times}$, das sind $q-1$ Stück. Es folgt $\displaystyle \binom{n}{1}_q = \frac{q^n-1}{q-1} = q^{n-1} + \cdots + q + 1.$ Wir sehen insbesondere, dass $\smash{\binom{n}{k}_q}$ tatsächlich von $q$ abhängt, und dass die Berechnung komplizierter als für $\binom{n}{k}$ ist. Binomialkoeffizienten sind bekanntlich symmetrisch: es gilt $\displaystyle \binom{n}{k} = \binom{n}{n-k}.$ Der kombinatorische Beweis besteht darin, dass man jeder Teilmenge ihr Komplement zuordnet. So etwas ähnliches können wir auch mit Unterräumen machen: Es gibt für jeden $n$-dimensionalen $\IF$-Vektorraum $V$ eine natürliche Bijektion zwischen den Unterräumen von $V$ und den Unterräumen des Dualraumes $V^*$ (der ebenfalls $n$-dimensional ist). Dabei ordnet man einem Unterraum $U \subseteq V$ den Unterraum $U^{\perp} = \{f \in V^* : f|_U = 0\}$ zu. Wenn $W$ ein Komplement von $U$ ist, dann gilt offenbar $U^{\perp} \cong W^*$. Daraus folgt $\dim(U^{\perp})=\dim(W) = n - \dim(U)$. Unter der Bijektion entsprechen die $k$-dimensionalen Unterräume von $V$ daher den $n-k$-dimensionalen Unterräumen von $V^*$. Wenden wir das auf $\IF_q$ an, erhalten wir direkt die Symmetrie-Gleichung $\displaystyle \binom{n}{k}_q = \binom{n}{n-k}_q.$ Ein wichtiges Hilfsmittel zur Berechnung der Binomialkoeffizienten ist die Rekursionsgleichung $\displaystyle \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}.$ Dafür gibt es auch einen einfachen kombinatorischen Beweis. Etwas ähnliches müssen wir uns nun für Unterräume überlegen. Sei dazu $V$ ein $n+1$-dimensionaler $\IF$-Vektorraum (an dieser Stelle kann $\IF$ irgendein Körper sein) und $U$ ein $k$-dimensionaler Unterraum von $V$. Sei $L \subseteq V$ irgendein $1$-dimensionaler Unterraum. Für den Durchschnitt $U \cap L \subseteq L$ gibt es zwei Möglichkeiten: Wenn $U \cap L = L$, ist $L \subseteq U$. Es gibt nun aber eine Bijektion zwischen den Unterräumen, die $L$ umfassen, und den Unterräumen von $V/L$. Konkret entspricht $U$ dem Unterraum $U/L$ von $V/L$, und es gilt $\dim(U/L)=k-1$ sowie $\dim(V/L) =n$. Wir zählen also $k-1$-dimensionale Unterräume eines $n$-dimensionalen Vektorraumes. Ansonsten ist $U \cap L = 0$. Das bedeutet, dass $U \to V \to V/L$ injektiv ist. Das Bild ist also ein $k$-dimensionaler Unterraum von $V/L$. Aber auch andere Unterräume $U'$ mit $U' \cap L=0$ können dasselbe Bild in $V/L$ haben. Genauer gesagt ist das Bild ja $(U+L)/L$ bzw. $(U'+L)/L$, sodass wir als Kriterium dafür $U+L = U'+L$ haben. Es ist also $U'$ ein Komplement von $L$ in $U \oplus L$. Nun brauchen wir: Zum Beweis des Lemmas: Wenn $f : U \to L$ eine lineare Abbildung ist, dann ist ihr Graph $W=\{u + f(u) : u \in U\} \subseteq U \oplus L$ ein Komplement von $L$: Für $u \in U$ ist $u = (u + f(u)) - f(u) \in W+L$, sodass $U \subseteq W+L$ und damit $U \oplus L = W+L$. Wenn $w \in W \cap L$, schreiben wir $w=u + f(u)$ mit $u \in U$ und folgern $u \in U \cap L = 0$, also $u=0$ und weiter $w=0$. Sei umgekehrt $W \subseteq U \oplus L$ ein Komplement von $L$. Für $u \in U$ gibt es wegen $U \subseteq U \oplus L = W \oplus L$ ein eindeutiges $f(u) \in L$ mit $u + f(u) \in W$. Dies definiert eine lineare Abbildung $f : U \to L$, und nach Konstruktion ist $u + f(u) \in W$ für alle $u \in U$. Ist umgekehrt $w \in W$, etwa $w = u + l$ mit $u \in U$ und $l \in L$, so ist $f(u) = l$ und daher $w = u + f(u)$. $\checkmark$ In unserem Fall hat der Vektorraum der linearen Abbildungen $U \to L$ die Dimension $\dim(U) \cdot \dim(L) = k$ und folglich genau $q^k$ Elemente, wenn $\IF=\IF_q$. Wir haben also eine Bijektion zwischen den $k$-dimensionalen Unterräumen $U$ mit $U \cap L = 0$ und den jeweils $q^k$-fach gezählten $k$-dimensionalen Unterräumen von $V/L$ gefunden. Damit gilt: $\displaystyle (1) \qquad \binom{n+1}{k}_q = \binom{n}{k-1}_q + q^k \cdot \binom{n}{k}_q$ Die Formel gilt auch für $k=0$, wenn wir $\smash{\binom{n}{k}_q=0}$ für $k<0$ vereinbaren, was wir ab sofort tun werden. Mit diesen Resultaten können wir nun alle $q$-Binomialkoeffizienten rekursiv ausrechnen. Zum Beispiel: $\displaystyle \binom{2}{0}_q = \binom{2}{2}_q = 1, \quad \binom{2}{1}_q = q+1.$ $\displaystyle \binom{3}{0}_q = \binom{3}{3}_q = 1, \quad \binom{3}{1}_q = \binom{3}{2}_q = q^2+q+1. $ $\displaystyle \binom{4}{0}_q = \binom{4}{4}_q = 1, \quad \binom{4}{1}_q = \binom{4}{3}_q = q^3+q^2+q+1 = (q+1)(q^2+1),$ $\displaystyle \binom{4}{2}_q = \binom{3}{1}_q + q^2 \cdot \binom{3}{2}_q = (q^2+1)(q^2+q+1).$ $\displaystyle \binom{5}{0}_q = \binom{5}{5}_q = 1, \quad \binom{5}{1}_q = \binom{5}{4}_q = q^4+q^3+q^2+q+1,$ $\displaystyle \binom{5}{2}_q = \binom{5}{3}_q = \binom{4}{1}_q + q^2 \cdot \binom{4}{2}_q = (q+1)(q^2+1) + q^2 (q^2+1)(q^2+q+1) = (q^2+1)(q^4+q^3+q^2+q+1).$ Per Induktion folgt auch, dass $\binom{n}{k}_q$ stets ein polynomieller Ausdruck in $q$ (mit Koeffizienten in $\IN$) ist. Binomialkoeffizienten erfüllen noch eine weitere Rekursionsregel: $\displaystyle k \cdot \binom{n}{k} = n \cdot \binom{n-1}{k-1}$ Dafür gibt es einen einfachen kombinatorischen Beweis, den wir wieder auf Vektorräume übertragen können: Ist $V$ ein $n$-dimensionaler $\IF_q$-Vektorraum und $k \geq 0$, so gibt es eine Bijektion $\{(v,U) : U \subseteq V \text{ Unterraum},\, \dim(U)=k,\, 0 \neq v \in U\} \cong \{(v,W) : 0 \neq v \in V,\, W \subseteq V/ \langle v \rangle \text{ Unterraum},\, \dim(W)=k-1\},$ nämlich $(v,U) \mapsto (v,U/ \langle v \rangle)$. Daraus folgt $\displaystyle (2) \qquad (q^k-1) \cdot \binom{n}{k}_q = (q^n-1) \cdot \binom{n-1}{k-1}_q$ bzw. falls $k > 0$ $\displaystyle (2') \qquad \binom{n}{k}_q = \frac{q^n-1}{q^k-1} \cdot \binom{n-1}{k-1}_q.$ Mit (2) können wir auch eine Rekursionsgleichung für die Anzahl $\displaystyle G_q(n) := \sum_{k \geq 0} \binom{n}{k}_q$ aller Unterräume eines $n$-dimensionalen $\IF_q$-Vektorraumes aufstellen: Wir berechnen dazu $\displaystyle \binom{n+1}{k}_q = \binom{n}{k-1}_q + q^k \cdot \binom{n}{k}_q = \binom{n}{k-1}_q + \binom{n}{k}_q + (q^k-1) \cdot \binom{n}{k}_q = \binom{n}{k-1}_q + \binom{n}{k}_q + (q^n-1) \cdot \binom{n-1}{k-1}_q.$ Summieren über alle $k \geq 0$ liefert $\displaystyle (3) \qquad G_q(n+1) = 2 \cdot G_q(n) + (q^n-1) \cdot G_q(n-1).$ Die Anfangswerte sind $G_q(0)=1$ und $G_q(1)=2$. Aus (2') folgt schließlich auch induktiv eine Produktformel für die $q$-Binomialkoeffizienten, nämlich $\displaystyle (4) \qquad \binom{n}{k}_q = \frac{(q^n-1) \cdot (q^{n-1}-1) \cdots (q^{n-k+1}-1)}{(q^k-1) \cdot (q^{k-1}-1) \cdots (q-1)},$ die analog zur expliziten Formel $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$ ist. Sie kann auch so bewiesen werden: Ein $k$-dimensionaler Unterraum von $V$, wobei $\dim(V)=n$, wird von $k$ linear unabhängigen Vektoren $v_1,\dotsc,v_k$ erzeugt. Für $v_1$ gibt es $q^n-1$ Möglichkeiten. Für $v_2$ müssen wir einen Vektor in $V \setminus \langle v_1 \rangle$ nehmen, sodass es $q^n-q$ Möglichkeiten gibt. Für $v_3$ müssen wir einen Vektor in $V \setminus \langle v_1,v_2 \rangle$ nehmen, wofür es $q^n-q^2$ Möglichkeiten gibt, usw. Es gibt also genau $(q^n-1) \cdot (q^n-q) \cdots (q^n-q^{k-1})$ Tupel von $k$ linear unabhängigen Vektoren in $V$. Für $k=n$ erhalten wir insbesondere die Anzahl der geordneten Basen von $V$. Ein $k$-dimensionaler Unterraum von $V$ hat also $(q^k-1) \cdot (q^k-q) \cdots (q^k-q^{k-1})$ geordnete Basen. Es folgt: $\displaystyle \binom{n}{k}_q = \frac{(q^n-1) \cdot (q^n-q) \cdots (q^n-q^{k-1})}{(q^k-1) \cdot (q^k-q) \cdots (q^k-q^{k-1})} = \frac{(q^n-1) \cdot (q^{n-1}-1) \cdots (q^{n-k+1}-1)}{(q^k-1) \cdot (q^{k-1}-1) \cdots (q-1)}$ Die evidenten Analogien zwischen $n$-elementigen Mengen (und ihren Teilmengen) und $n$-dimensionalen $\IF_q$-Vektorräumen (und ihren Unterräumen) gehen noch viel weiter und kann man auf verschiedene Weisen präzisieren. Zum einen kann man die Verbände der Teilmengen bzw. (projektiven) Unterräume gemeinsam axiomatisieren. Zum anderen kann man einen Körper mit einem Element $\IF_1$ definieren – natürlich muss dazu der übliche Körperbegriff stark erweitert werden – derart, dass $\IF_1$-Vektorräume dasselbe wie (punktierte) Mengen sind. Es gibt allerdings verschiedene Definitionen von $\IF_1$, die nicht äquivalent sind.

Allgemeine Definition von $q$-Binomialkoeffizienten

Die explizite Formel (4) kann benutzt werden, um $\smash{\binom{n}{k}_q}$ für beliebige $q \in \IN$ zu definieren, bzw. sogar für eine polynomielle Variable $q$. Mit dieser Definition ist $\smash{\binom{n}{k}_q}$ zunächst nur ein Bruch aus zwei Polynomen in dem Polynomring $\IZ[q]$. Man kann allerdings die Rekursionsgleichung (1) mit dieser Definition zeigen und induktiv folgern, dass $\smash{\binom{n}{k}_q}$ tatsächlich ein Polynom in $q$ mit Koeffizienten in $\IN$ ist. Die Menge solcher Polynome bezeichnen wir mit $\IN[q]$. Genauer gesagt handelt es sich bei $\IN[q]$ um einen Halbring (einem "Ring ohne Minus"), den freien Halbring auf einem Erzeuger. Ein ähnlicher Ansatz imitiert die Definition $\displaystyle \binom{n}{k} := \frac{n \cdot (n-1) \cdots (n-k+1)}{k!} = \frac{n!}{k! \cdot (n-k)!}.$ Es soll $\binom{n}{1}_q = q^{n-1}+\cdots+q+1$ sein. Für Binomialkoeffizienten (das ist gerade der Fall $q=1$, dazu später mehr) ist aber $\binom{n}{1} = n$. Wir können uns demnach $\displaystyle [n]_q := q^{n-1}+\cdots+q+1 = \frac{q^n-1}{q-1}$ als ein $q$-Analogon von $n$ vorstellen. Entsprechend sei $[n]_q ! := [n]_q \cdot [n-1]_q \cdots [1]_q$ das $q$-Analogon der Fakultät. Wir definieren damit $\displaystyle (5) \qquad \binom{n}{k}_q := \frac{[n]_q \cdot [n-1]_q \cdots [n-k+1]_q}{[k]_q \cdot [k-1]_q \cdots [1]_q} = \frac{[n]_q !}{[k]_q ! \cdot [n-k]_q !}.$ Natürlich ist das zu (4) äquivalent. A priori ist $\smash{\binom{n}{k}_q}$ also ein Bruch von zwei Polynomen in $\IN[q]$, aber die Gleichung $[k]_q + q^k [n-k]_q = [n]_q$ kann genutzt werden, um die Rekursionsgleichung (1) zu zeigen, womit also induktiv $\smash{\binom{n}{k}_q} \in \IN[q]$ folgt. Weil $[n]_q$ normiert vom Grad $n-1$ ist, ist $\binom{n}{k}_q$ normiert vom Grad $\displaystyle \deg \binom{n}{k}_q = \bigl((n-1)+(n-2)+\cdots+(n-k)\bigr) - \bigl((k-1)+\cdots+(k-k)\bigr) = k \cdot n - k \cdot k = k \cdot (n-k).$ Weil $\smash{\binom{n}{k}_q}$ ein Polynom in $q$ ist, können wir (zum Beispiel) jede natürliche Zahl für $q$ einsetzen. Wenn wir das nun für $q=1$ machen, ist einfach $[n]_1 = n$ und daher $\displaystyle \binom{n}{k}_1 = \binom{n}{k}.$ Die $q$-Binomialkoeffizienten enthalten also den gewöhnlichen Binomialkoeffizienten als Spezialfall (nämlich $q=1$). Das bedeutet auch, dass $\binom{n}{k}$ die Summe der Koeffizienten des Polynoms $\smash{\binom{n}{k}_q} \in \IN[q]$ ist. In diesem Sinne sind die $q$-Binomialkoeffizienten eine Verfeinerung der gewöhnlichen Binomialkoeffizienten. Allgemeiner kann man für $n=k_1+\cdots+k_s$ den $q$-Multinomialkoeffizienten definieren durch $\displaystyle \binom{n}{k_1,\dotsc,k_s}_q := \frac{[n]_q !}{[k_1]_q ! \cdot [k_2]_q ! \cdots [k_s]_q !}.$ Wegen der leicht zu beweisenden Rechenregel $\displaystyle \binom{n}{k_1,\dotsc,k_s}_q = \binom{n}{k_1}_q \cdot \binom{n-k_1}{k_2,\dotsc,k_s}_q$ ist auch der $q$-Multinomialkoeffizient ein Polynom in $q$. Wenn wir für $q$ eine Primzahlpotenz einsetzen, so ergibt sich außerdem, dass $\smash{\binom{n}{k_1,\dotsc,k_s}_q}$ die Anzahl der Filtrierungen $0 = U_0 \subseteq U_1 \subseteq U_2 \subseteq \cdots \subseteq U_s = V$ eines $n$-dimensionalen $\IF_q$-Vektorraumes $V$ ist, für die $\dim(U_i/U_{i-1}) = k_i$ gilt. Für $k_i=1$ folgt insbesondere, dass $[n]_q !$ die Anzahl der vollständigen Fahnen von $V$ ist.

Nicht-kommutativer Binomialsatz

Es sei $R$ ein Halbring (oder sogar ein Ring, aber wir werden hier nirgendwo subtrahieren) mit zwei Elementen $x,y$. Wenn $x,y$ miteinander kommutieren, dann gilt der gewöhnliche Binomialsatz $\displaystyle (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}.$ Wenn $x,y$ nicht miteinander kommutieren, ist die Lage komplizierter. Ausmultiplizieren von $(x+y)^n$ liefert die Summe aller Wörter in $x,y$ der Länge $n$. Für $n=9$ ist etwa $x^2 y x^3 y^2 x$ ein solches Wort. Wenn wir nun aber ein Element $q$ haben, welches im Zentrum von $R$ liegt (also mit allen Elementen vertauscht) und außerdem die Vertauschungsregel $yx = qxy$ erfüllt (zum Beispiel $q=1$ im kommutativen Fall), so kann man induktiv jedes Wort auf die Gestalt $x^i y^j$ bringen. Dazu muss man sich nur allgemeiner $y^i x^j = q^{i \cdot j} x^j y^i$ überlegen. Für das Beispielwort oben erhalten wir $x^2 y x^3 y^2 x = q^6 x^6 y^3.$ Das universelle Beispiel für einen Halbring mit drei solchen Elementen ist $\IN[q] \langle x,y \rangle / \langle yx = qxy \rangle$. Hier lässt sich jedes Element sogar eindeutig als $\IN[q]$-Linearkombination von Worten der Form $x^i y^j$ schreiben. Beim Ausmultiplizieren von $(x+y)^n$ kommen Wörter $x^k y^{n-k}$ in der Regel öfter vor. Zum Beispiel gilt $(x+y)^2 = x^2+xy+yx+y^2=x^2+(q+1)xy+y^2.$ Allgemeiner gilt nun der folgende nicht-kommutative Binomialsatz (oder auch $q$-Binomialsatz): $\displaystyle (6) \qquad (x+y)^n = \sum_{k=0}^{n} \binom{n}{k}_q x^k y^{n-k} \qquad (\text{wenn } yx=qxy)$ Beweisen wir das mit Induktion (genauso wie den gewöhnlichen Binomialsatz, welcher den Spezialfall $q=1$ darstellt). Der Induktionsanfang ist $n=0$ einfach. Im Induktionsschritt verwenden wir einfach die Rekursionsgleichung (1): $\begin{align*} (x+y)^{n+1} & = x (x+y)^n + y (x+y)^n \\ & = \sum_{k=0}^{n} \binom{n}{k}_q x^{k+1} y^{n-k} + \sum_{k=0}^{n} \binom{n}{k}_q y x^k y^{n-k} \qquad (\text{nutze }y x^k = q^k x^k y)\\ & = \sum_{k=0}^{n} \binom{n}{k}_q x^{k+1} y^{n-k} + \sum_{k=0}^{n} \binom{n}{k}_q q^k x^k y^{n+1-k} \\ & = \sum_{k=0}^{n} \binom{n}{k-1}_q x^{k} y^{n+1-k} + \sum_{k=0}^{n+1} \binom{n}{k}_q q^k x^k y^{n+1-k} \\ & = \sum_{k=0}^{n+1} \left(\binom{n}{k-1}_q + q^k \binom{n}{k}_q\right) x^k y^{n+1-k} \\ & = \sum_{k=0}^{n+1} \binom{n+1}{k}_q x^k y^{n+1-k} \end{align*}$ Wir könnten daher auch alternativ $\smash{\binom{n}{k}_q \in \IN[q]}$ als den Koeffizienten von $x^k y^{n-k}$ in $(x+y)^n$ definieren für das universelle Beispiel $\IN[q] \langle x,y \rangle / \langle yx = qxy \rangle$. Im gewöhnlichen Binomialsatz kann man $x=y=1$ substitutieren und erhält $\smash{2^n = \sum_{k=0}^{n}\binom{n}{k}}$. Das ist hier nicht möglich, weil $x=y=1$ die Relation $yx=qxy$ nicht erfüllen. Allgemeiner gilt der folgende nicht-kommutative Multinomialsatz: $\displaystyle (6') \qquad (x_1+\cdots+x_s)^n = \sum_{k_1+\cdots+k_s=n} \binom{n}{k_1,\dotsc,k_s}_q x_1^{k_1} \cdots x_s^{k_s} \qquad (\text{wenn } i < j \implies x_j x_i =q x_i x_j)$ Der Beweis (per Induktion nach $s$) benutzt den Binomialsatz für $(x_1+(x_2+\cdots+x_s))^n$. Aus dem nicht-kommutativen Binomialsatz kann man übrigens schnell die $q$-Vandermonde-Identität ableiten.

Erzeugende Funktion

Für eine Zahlenfolge ist es immer hilfreich, ihre erzeugende Funktion zu kennen. Das ist bei $q$-Binomialkoeffizienten $\smash{\binom{n}{k}_q}$ zumindest möglich, wenn wir noch den Faktor $q^{k(k-1)/2}$ ergänzen: $\displaystyle (7) \qquad \sum_{k=0}^{n} q^{k(k-1)/2} \binom{n}{k}_q \, T^k = \prod_{i=0}^{n-1} (1+q^i T)$ Die Gleichung wird manchmal auch als $q$-Binomialsatz bezechnet. Sie lässt sich per Induktion nach $n$ beweisen. Im Induktionsschritt berechnen wir mit Hilfe von (1): $\begin{align*} \sum_{k=0}^{n+1} q^{k(k-1)/2} \binom{n+1}{k}_q \, T^k & = \sum_{k=0}^{n+1} q^{k(k-1)/2} \binom{n}{k-1}_q \, T^k + \sum_{k=0}^{n+1} q^{k(k-1)/2} q^k \binom{n}{k}_q \, T^k \\ & = \sum_{k=0}^{n} q^{k(k+1)/2} \binom{n}{k}_q \, T^{k+1} + \sum_{k=0}^{n} q^{k(k-1)/2} q^k \binom{n}{k}_q \, T^k \\ & = \sum_{k=0}^{n} q^{k(k-1)/2} \binom{n}{k}_q \, (qT)^k T + \sum_{k=0}^{n} q^{k(k-1)/2} \binom{n}{k}_q \, (qT)^k \\ & = (1+T) \sum_{k=0}^{n} q^{k(k-1)/2} \binom{n}{k}_q \, (qT)^k \\ & = (1+T) \prod_{i=0}^{n-1} (1+q^i qT) \\ & = \prod_{i=0}^{n} (1+q^i T) \end{align*}$ Es gibt noch zahlreiche andere erzeugenden Funktionen mit $q$-Binomialkoeffizienten, aber belassen wir es einmal bei dieser hier.

Kombinatorische Interpretationen

Die Koeffizienten des Polynoms $\smash{\binom{n}{k}_q \in \IN[q]}$ lassen sich auf mehrere Weisen kombinatorisch interpretieren. Die entsprechenden Beweise lassen sich per Induktion führen (und hängen auch eng mit der bereits besprochenen erzeugenden Funktion und dem nicht-kommutativen Binomialsatz zusammen), aber wir wählen hier einen anderen Ansatz, der mit Vektorräumen über einem endlichen Körper $\IF_q$ arbeitet und sogar die Interpretationen herleitet. Wir müssen also $q$ als Primzahlpotenz annehmen, aber um polynomielle Gleichungen zu zeigen, reicht dies völlig aus. Bei allen diesen kombinatorischen Interpretationen handelt es sich um Verfeinerungen von bekannten kombinatorischen Interpretationen des gewöhnlichen Binomialkoeffizienten. Sei zunächst $\IF$ ein beliebiger Körper und $U$ ein $k$-dimensionaler Unterraum von $\IF^n$. Wir behaupten, dass $U$ eine eindeutig bestimmte Basis $(u_1,\dotsc,u_k)$ mit den folgenden Eigenschaften besitzt: Für die natürlichen Zahlen $n_i = \min \{j : u_{i,j} \neq 0\}$ gilt: • $n_i < n_{i+1}$ • $u_{i,n_i} = 1$ • $u_{j,n_i}=0$ für $j \neq i$ Das bedeutet gerade, dass die zugehörige $k \times n$-Matrix in reduzierter Zeilenstufenform (auch bekannt als Treppennormalform) ist. Die $n_i$ sind die Indizes der Pivotspalten. Hier ein Beispiel (wobei die frei wählbaren Einträge mit $\star$ gekennzeichnet sind): $\begin{pmatrix} 0 & 0 & 1 & \star & \star & 0 & 0 & \star & \star & 0 & \star\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & \star & \star & 0 & \star\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & \star & \star & 0 & \star\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \star \end{pmatrix}$ Hier ist $n=11$, $k=4$, und die natürlichen Zahlen $n_i$ sind $3 < 6 < 7 < 10$. Skizzieren wir den Beweis (auch wenn es nur lineare Algebra ist, und wer bereits die reduzierte Zeilenstufenform kennt, kann den Beweis überspringen): Wenn $U=0$ bzw. $k=0$, sind wir fertig. Andernfalls existiert $n_1 := \min \{j : \exists v \in U (v_j \neq 0)\}$ und damit ein $u_1 \in U$ mit $u_{1,n_1} = 1$. Es folgt $u_{1,j}=0$ für $ j < n_i$. Wenn $U = \langle u_1 \rangle$ bzw. $k=1$, sind wir fertig. Andernfalls gibt es ein $v \in U \setminus \langle u_1 \rangle$, und für $v' := v - v_{n_1} u_1$ gilt dann $v' \neq 0$ und $v'_{n_1}=0$. Also existiert $n_2 := \min \{j : \exists v \in U (v_{n_1} = 0, \, v_j \neq 0)\}.$ Wähle $u_2 \in U$ mit $u_{2,n_1}=0$ und $u_{2,n_2}=1$. Natürlich gilt $n_1 < n_2$, und die Definition von $n_2$ impliziert $u_{2,j} = 0$ für $j < n_2$. Indem wir $u_1$ durch $u_1 - (u_1)_{n_2} u_2$ ersetzen, können wir $(u_1)_{n_2}=0$ annehmen. Jetzt machen wir genauso weiter: Wenn $U=\langle u_1,u_2\rangle$, sind wir fertig, und andernfalls existiert wieder $n_3 := \min \{j : \exists v \in U ( v_{n_1}=v_{n_2}=0,\, v_j \neq 0)\}$ und wir können ein $u_3 \in U$ wählen mit $u_{3,n_1}=u_{3,n_2}=0$ und $u_{3,n_3}=1$, usw. Soviel zur Existenz der Basis. Zur Eindeutigkeit sei $(u'_1,\dotsc,u'_k)$ eine Basis von $U$ mit den drei genannten Eigenschaften. Dann sieht man zunächst induktiv, dass die zugehörigen natürlichen Zahlen $n'_i$ mit $n_i = \min \{j : \exists v \in U ( v_{n_1}= \dotsc = v_{n_{i-1}}=0,\, v_j \neq 0)\}$ übereinstimmen. Schreibe $u'_i = \sum_p \lambda_{i,p} u_p$ mit $\lambda_{i,p} \in \IF$. Es folgt $\delta_{i,j} = u'_{i,n'_j} = u'_{i,n_j} = \sum_p \lambda_{i,p} u_{j,n_p} = \sum_p \lambda_{i,p} \delta_{j,p} = \lambda_{i,j}$ und damit $u'_i = u_i$. Wir haben damit eine Bijektion zwischen den $k$-dimensionalen Unterräumen von $\IF^n$ und den $k \times n$-Matrizen über $\IF$ in reduzierter Zeilenstufenform gefunden. Wenn wir die natürlichen Zahlen $n_1 < \cdots < n_k$, die Indizes der Pivotspalten, einmal festhalten, so haben wir in der $i$-ten Zeile $r_i := n - n_i - (k-i)$ frei zu vergebene, oben mit $\star$ markierte Einträge (man sagt auch Freiheitsgrade), weil die ersten $n_i$ Einträge durch $0,0,\dotsc,0,1$ festgelegt sind danach lediglich die $k-i$ Indizes der nachfolgenden Pivotspalten durch Nullen festgelegt sind. Die Relationen $n_i < n_{i+1}$ übersetzen sich zu $r_{i+1} \leq r_i$. Die Relationen $n_1 \geq 1$ und $n_k \leq n$ übersetzt sich zu $r_1 \leq n-k$ und $r_k \geq 0$. Es gilt demnach $n-k \geq r_1 \geq \cdots \geq r_{k-1} \geq r_k \geq 0.$ Insgesamt gibt es $r := r_1 + \cdots + r_k$ Freiheitsgrade, und die $r_i$ stellen eine Partition von $r$ dar. Ihre Länge ist höchstens $k$ (weil man bei einer Partition fordert, dass alle Zahlen $>0$ sind, das heißt wir müssen eventuell noch einige $ r_i$ hinten abschneiden), und ihre Bestandteile sind jeweils $\leq n-k$. Definieren wir daher $P(k,m,r)$ als die Menge der Partitionen von $r$ in höchstens $k$ Zahlen, die jeweils $\leq m$ sind, so gibt es eine Bijektion $\displaystyle \{k\text{-dimensionale Unterräume von } V\} \cong \coprod_{r \geq 0} P(k,n-k,r) \times \IF^r.$ Wenn speziell $\IF=\IF_q$ ein endlicher Körper ist, können wir die Kardinalitäten beider Mengen betrachten und erhalten $\displaystyle (8) \qquad \binom{n}{k}_q = \sum_{r \geq 0} p(k,n-k,r) \cdot q^r,$ wobei $p(k,m,r)$ die Kardinalität von $P(k,m,r)$ sei. Die Summe darf man auf $r \leq k(n-k)$ einschränken. Weil wir diese polynomielle Gleichung für alle Primzahlpotenzen $q$ bewiesen haben, stimmen die Polynome in $\IN[q]$ überein. Zum Beispiel ist der Koeffizient von $q^4$ in $\smash{\binom{5}{2}_q}$ gleich $2$, weil es $2$ Partitionen von $4$ der Länge $\leq 2$ mit Zahlen $\leq 3$ gibt, nämlich $4=2+2$ und $4=3+1$. Eine andere Schreibweise für (8) ist $\displaystyle (8') \qquad \binom{n}{k}_q = \sum_{\large {n-k \geq r_1 \geq \cdots \geq r_{k-1} \geq r_k \geq 0}} q^{r_1+\cdots+r_k}.$ Wir deuten kurz an, wie man sich (8) rechnerisch klarmachen kann: Aus der erzeugenden Funktion (7) kann man folgern, dass der Koeffizient von $q^r$ in $\smash{\binom{n}{k}_q}$ die Anzahl der Partitionen von $r + k(k+1)/2$ in $k$ verschiedene Zahlen ist, die alle $\leq n$ sind. Zieht man dabei $i$ von der $i$-ten Zahl (der Größe nach) ab, erhält man eine Partition von $r$ in höchstens $k$ Zahlen, die alle $\leq n-k$ sind. Tatsächlich ist (7) äquivalent zu (8). Eine andere kombinatorische Interpretation erkennt man, wenn man einmal die Pivotspalten aus der Matrix in reduzierter Zeilenstufenform entfernt. Im obigen Beispiel: $\begin{pmatrix} 0 & 0 & \star & \star & \star & \star & \star\\ 0 & 0 & 0 & 0 & \star & \star & \star\\ 0 & 0 & 0 & 0 & \star & \star & \star\\ 0 & 0 & 0 & 0 & 0 & 0 & \star \end{pmatrix}$ Es entsteht eine $k \times (n-k)$-Matrix mit $r$ frei wählbaren Einträgen. Damit die Koordinaten gleich etwas einfacher werden, rotieren wir die Matrix im Uhrzeigersinn: $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \star \\ 0 & 0 & 0 & \star \\ 0 & \star & \star & \star \\ 0 & \star & \star & \star \\ \star & \star & \star & \star \end{pmatrix}$ Die Anordnung der frei wählbaren Einträge können wir auch durch einen Gitterweg von $(0,0)$ nach $(k,n-k)$ kodieren, wobei jeder Schritt nach rechts oder oben geht: $\backslash begin\{tikzpicture\}[scale=0.5]\; \backslash fill\; [blue!10!white]\; (0,0)\; --\; (0,1)\; --\; (1,1)\; --\; (1,3)\; --\; (3,3)\; --\; (3,5)\; --\; (4,5)\; --\; (4,7)\; --\; (4,0)\; --\; (0,0);\; \backslash draw\; [black!40!white]\; (0,0)\; grid\; (4,7);\; \backslash draw\; [blue!60!black,thick]\; (0,0)\; --\; (0,1)\; --\; (1,1)\; --\; (1,3)\; --\; (3,3)\; --\; (3,5)\; --\; (4,5)\; --\; (4,7);\; \backslash end\{tikzpicture\}$ Dabei wird nach unten eine Fläche von $r$ Einheiten eingeschlossen. Definieren wir also $w(k,m,r)$ als die Anzahl der Gitterwege von $(0,0)$ nach $(k,m)$, deren Schritte nach rechts oder oben gehen und die eine Fläche von $r$ Einheiten nach unten einschließen, so haben wir gezeigt: $\displaystyle (9) \qquad \binom{n}{k}_q = \sum_{r \geq 0} w(k,n-k,r) \cdot q^r.$ Auch diese Gleichung gilt wieder automatisch in $\IN[q]$. Setzen wir $q=1$ ein, erhalten wir die bekannte Interpretation von $\binom{n}{k}$ als die Anzahl der Gitterwege ohne Festlegung einer Fläche. Für $ k > n$ gelten (8) und (9) ebenfalls, dann sind halt beide Seiten $0$. Es gibt noch eine andere Interpretation von $w(k,m,r)$. Bezeichnen wir dazu einmal jeden Schritt nach rechts mit $X$, und jeden Schritt nach oben mit $Y$. Der Gitterweg oben ist entsprechend $YXYYXXYYXYY$. Allgemein bekommen wir ein Wort in $X,Y$, in dem $X$ genau $k$-mal und $Y$ genau $m$-mal vorkommt. Wie kann man nun die eingeschlossene Fläche anhand des Wortes ausdrücken? Offenbar entspricht jede Einheit in der Fläche einem Paar von Buchstaben $\cdots Y \cdots X \cdots$ in dem Wort: $\backslash def\backslash xlabel\{\backslash text\{\backslash textcolor\{black\}\{\backslash footnotesize\; \$X\$\}\}\}\; \backslash def\backslash ylabel\{\backslash text\{\backslash textcolor\{black\}\{\backslash footnotesize\; \$Y\$\}\}\}\; \backslash def\backslash xlabelmark\{\backslash text\{\backslash textcolor\{red\}\{\backslash footnotesize\; \$X\$\}\}\}\; \backslash def\backslash ylabelmark\{\backslash text\{\backslash textcolor\{red\}\{\backslash footnotesize\; \$Y\$\}\}\}\; \backslash begin\{tikzpicture\}[scale=0.8]\; \backslash fill\; [blue!10!white]\; (0,0)\; --\; (0,1)\; --\; (1,1)\; --\; (1,3)\; --\; (3,3)\; --\; (3,5)\; --\; (4,5)\; --\; (4,7)\; --\; (4,0)\; --\; (0,0);\; \backslash fill\; [red!20!white]\; (2,1)\; --\; (3,1)\; --\; (3,2)\; --\; (2,2)\; --\; (2,1);\; \backslash draw\; [black!40!white]\; (0,0)\; grid\; (4,7);\; \backslash draw\; [blue!60!black,thick]\; (0,0)\; --node[right]\{\backslash ylabel\}\; (0,1)\; --node[above]\{\backslash xlabel\}\; (1,1)\; --node[right]\{\backslash ylabelmark\}\; (1,2)\; --node[right]\{\backslash ylabel\}\; (1,3)\; --node[above]\{\backslash xlabel\}\; (2,3)\; --node[above]\{\backslash xlabelmark\}\; (3,3)\; --node[right]\{\backslash ylabel\}\; (3,4)\; --node[right]\{\backslash ylabel\}\; (3,5)\; --node[above]\{\backslash xlabel\}\; (4,5)\; --node[right]\{\backslash ylabel\}\; (4,6)\; --node[right]\{\backslash ylabel\}\; (4,7);\; \backslash end\{tikzpicture\}$ Ist allgemeiner $\Sigma$ ein geordnetes Alphabet (in unserem Fall $\{X < Y\}$) und $w = w_1 \cdots w_n$ mit $w_i \in \Sigma$ ein Wort in $\Sigma$, so ist eine Inversion von $w$ ein Paar von Indizes $i < j$ mit $w_i > w_j$. Die eingeschlossene Fläche ist also nichts weiter als die Anzahl der Inversionen des Wortes. Wir haben damit gezeigt, dass $w(k,m,r)$ auch die Anzahl der Worte in $X,Y$ mit $k$ Vorkommen von $X$ und $m$ Vorkommen in $Y$ und $r$ Inversionen ist. Diese Beschreibung lässt sich auch in die Gleichung (9) einsetzen. Noch allgemeiner kann man für $n=k_1 + \cdots + k_s$ zeigen: $\displaystyle (10) \qquad \binom{n}{k_1,\dotsc,k_s}_q = \sum_{r\geq 0} w(k_1,\dotsc,k_s,r) \cdot q^r$ Dabei sei $w(k_1,\dotsc,k_s,r)$ die Anzahl der Worte in dem geordneten Alphabet $\{X_1 < \dotsc < X_s\}$ mit $k_i$ Vorkommen von $X_i$ und $r$ Inversionen. Tatsächlich ist (10) zum $q$-Multinomialsatz (6') äquivalent; dazu muss man sich induktiv klarmachen, dass jedes Wort der Länge $n$, welches also beim Ausmultiplizieren von $(x_1+\cdots+x_s)^n$ entsteht, auf die Form $q^r x_1^{k_1} \cdots x_s^{k_s}$ gebracht werden kann, wobei $r$ die Zahl der Inversionen ist.

Quellen

Danke an ligning fürs Korrekturlesen!