Abzählende Kombinatorik

Gegenstand und Bedeutung

Die abzählende Kombinatorik ist ein Teilbereich der Kombinatorik. Sie bestimmt, wie viele mögliche Anordnungen oder Auswahlen von Objekten es gibt. Dabei sind zwei Fragen entscheidend: Sind die Objekte unterscheidbar oder dürfen gleiche Objekte mehrfach vorkommen? Und ist die Reihenfolge wichtig (geordnet) oder unwichtig (ungeordnet)?

In der modernen Kombinatorik lassen sich solche Anordnungen und Auswahlen als Abbildungen auffassen; die zentrale Aufgabe besteht dann im Zählen dieser Abbildungen. Die Kombinatorik ist außerdem eine wichtige Grundlage für Wahrscheinlichkeitsrechnungen nach dem Laplace-Begriff.

Schon wenige Objekte können extrem viele Möglichkeiten erzeugen. Beim Zauberwürfel lassen sich die 26 Elemente beispielsweise auf rund 43 Trillionen Arten kombinieren. Diese starke Zunahme heißt kombinatorische Explosion und ist auch Ursache des Geburtstagsparadoxons.

Geordnete und ungeordnete Auswahlen

Eine Permutation ist die Vertauschung der Reihenfolge einer Menge von n unterscheidbaren Elementen. Werden nur k<n Elemente in einer bestimmten Reihenfolge ausgewählt, heißt dies meist Variation oder geordnete Stichprobe; besonders im englischsprachigen Raum wird es teils ebenfalls Permutation genannt. Eine Auswahl ohne Beachtung der Reihenfolge heißt ungeordnete Stichprobe oder Kombination.

Damit gilt: Permutationen und Variationen sind geordnet, Kombinationen ungeordnet. Ob eine Permutation als Sonderfall einer Variation betrachtet wird, ist je nach Autor unterschiedlich.

Bei einer Auswahl ohne Wiederholung sind die ausgewählten Elemente paarweise verschieden; im Urnenmodell entspricht dies einer Stichprobe ohne Zurücklegen. Bei einer Auswahl mit Wiederholung dürfen gleiche Elemente mehrfach vorkommen; dies entspricht einer Stichprobe mit Zurücklegen.

Für k=n gibt es Permutationen ohne bzw. mit Wiederholung. Für k<n gibt es Variationen ohne bzw. mit Wiederholung. Ungeordnete Auswahlen heißen Kombinationen ohne Wiederholung beziehungsweise Kombinationen mit Wiederholung. Die englischen Bezeichnungen sind unter anderem n-permutation bzw. n-tuple, k-permutation bzw. k-tuple, k-combination und k-multiset.

Wichtige Zählformeln

Es seien n die vorhandenen Elemente, k die Zahl der ausgewählten Elemente und k_1,\ldots,k_s die Anzahlen nicht unterscheidbarer Elemente.

Für Permutationen ohne Wiederholung gilt n!. Gibt es Wiederholungen, so ist die Anzahl \frac{(k_1+\ldots+k_s)!}{k_1!\cdot\ldots\cdot k_s!}=\frac{n!}{k_1!\cdot\ldots\cdot k_s!}=\binom{n}{k_1,\ldots,k_s}. Dabei steht n! für die Fakultät und \binom{n}{k_1,\ldots,k_s} für einen Multinomialkoeffizienten.

Für Variationen ohne Wiederholung gilt n^{\underline{k}}=\binom{n}{k}\cdot k!=\frac{n!}{(n-k)!}. n^{\underline{k}} heißt fallende Fakultät. Variationen mit Wiederholung haben die Anzahl n^k; sie entsprechen k-Tupeln.

Für Kombinationen ohne Wiederholung gilt \binom{n}{k}=\frac{n!}{(n-k)!\cdot k!}. Sie entsprechen k-Teilmengen. Für Kombinationen mit Wiederholung gilt \left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!}; sie entsprechen Multimengen.

Verteilungen von Bällen auf Fächer

Das Modell „Bälle und Fächer“, auch Twelvefold Way genannt, verallgemeinert das Urnenmodell. Gesucht ist die Anzahl der Verteilungen von k Bällen auf n Fächer. Bälle und Fächer können jeweils unterscheidbar oder nicht unterscheidbar sein. Zusätzlich kann es keine Beschränkung geben, pro Fach höchstens einen Ball geben oder pro Fach mindestens einen Ball geben.

Sind Bälle und Fächer unterscheidbar, ergeben sich ohne Beschränkung n^k, bei höchstens einem Ball je Fach n^{\underline{k}}=\frac{n!}{(n-k)!}=k!\binom{n}{k}, und bei mindestens einem Ball je Fach n!\,S_{k,n}.

Sind die Bälle nicht unterscheidbar, die Fächer aber unterscheidbar, lauten die Anzahlen \left(\!\!\binom{n}{k}\!\!\right)=\binom{k+n-1}{n-1}, \binom{n}{k} und \left(\!\!\binom{n}{k-n}\!\!\right)=\binom{k-1}{n-1}.

Sind Bälle unterscheidbar und Fächer nicht unterscheidbar, erhält man \sum_{r=0}^{n}S_{k,r}, bei höchstens einem Ball je Fach 1 für k\leq n und 0 für k>n, sowie bei mindestens einem Ball je Fach S_{k,n}. Sind beide nicht unterscheidbar, lauten die Werte \sum_{r=0}^{n}P_{k,r}=P_{k+n,n}, wieder 1 für k\leq n beziehungsweise 0 für k>n, und P_{k,n}.

S_{k,n} ist die Stirling-Zahl zweiter Art: die Anzahl der Aufteilungen einer k-elementigen Menge in n nichtleere disjunkte Teilmengen. P_{k,n} zählt Darstellungen von k als Summe von n positiven ganzen Zahlen ohne Beachtung der Reihenfolge.

Äquivalente Summendarstellungen

In einem diskreten Wahrscheinlichkeitsraum (\Omega,P) können kombinatorische Formeln durch eine vollständige Zerlegung des Ereignisraums in disjunkte Ereignisse äquivalent dargestellt werden. Dazu werden k Bälle zufällig auf n\leq k Fächer verteilt und E_j als das Ereignis betrachtet, dass genau j Fächer mindestens einen Ball enthalten.

Bei nicht unterscheidbaren Bällen und unterscheidbaren Fächern ergibt sich |\Omega|=\binom{n+k-1}{k}=\sum_{j=1}^{n}\binom{n}{j}\binom{k-1}{k-j}.

Bei unterscheidbaren Bällen und unterscheidbaren Fächern gilt |\Omega|=n^k=\sum_{j=1}^{n}\binom{n}{j}\sum_{i=0}^{j-1}(-1)^i\binom{j}{j-i}(j-i)^k=\sum_{j=1}^{n}\binom{n}{j}(-1)^j\sum_{i=1}^{j}(-1)^i\binom{j}{i}i^k. Die zweite Summe entsteht durch Umkehrung der Summierungsreihenfolge beziehungsweise durch i\to j-i.

Für n=k bedeutet „alle Fächer enthalten mindestens einen Ball“ zugleich „alle Fächer enthalten genau einen Ball“. Dieses Ereignis hat n! Elemente. Daher folgt n!=\sum_{i=0}^{n-1}(-1)^i\binom{n}{n-i}(n-i)^n=(-1)^n\sum_{i=1}^{n}(-1)^i\binom{n}{i}i^n.