Kombinatorik

In der Kombinatorik wird untersucht, wie viele unterschiedliche Möglichkeiten sich bei der Anordnung einer bestimmten Anzahl an Objekten ergeben, je nachdem, ob dabei die Reihenfolge der Objekte berücksichtigt wird und/oder die Objekte wiederholt auftreten können.

Permutationen

Eine Menge mit n Elementen soll unter Berücksichtigung der Reihenfolge angeordnet werden, wobei jedes Element nur einmal vorkommen darf. Wie viele verschiedene Anordnungen sind dabei möglich?

Diese Grundfrage lässt sich beantworten, indem Schritt für Schritt geprüft wird, wie viele Möglichkeiten sich bei der Besetzung jeder einzelnen Stelle ergeben. Für die Besetzung der ersten Stelle gibt es n Möglichkeiten, da noch kein Element vergeben wurde. Für die Besetzung der zweiten Stelle bleiben nur noch n-1 Möglichkeiten, da ein Element bereits an der ersten Stelle vergeben wurde. Für die Besetzung der dritten Stelle bleiben entsprechend noch n-2 Möglichkeiten, und so weiter. Für die letzte Stelle bleibt nur noch ein Element übrig, somit gibt es auch nur eine Möglichkeit die Stelle zu besetzen.

Jede Besetzung einer einzelnen Stelle kann mit jeder Besetzung einer anderen Stelle kombiniert werden. Damit entspricht die Anzahl an n-Permutationen, d.h. an Anordnungen mit Berücksichtigung der Reihenfolge und ohne Wiederholung der Elemente, dem Produkt aller Möglichkeiten für die einzelnen Stellen:

(1)n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1

Dabei wird mit n! (gelesen: n Fakultät) die Produktfolge von 1 bis n bezeichnet.

Beispiel:

  • Auf wie viele verschiedene Arten lassen sich ein roter, ein grüner, ein blauer, ein gelber und ein weißer Ball in einer Reihe hintereinander legen?

    Da es sich insgesamt um fünf Bälle handelt und jeder Ball die erste Position in der Reihe einnehmen kann, gibt es für die Besetzung der ersten Stelle 5 Möglichkeiten. Für jede mögliche Besetzung der ersten Stelle gibt es 4 Möglichkeiten, die zweite Stelle zu besetzen, und für jede dieser Anordnungen existieren wiederum 3 Möglichkeiten zur Besetzung der dritten Stelle. Schließlich gibt es für jede dieser Anordnungen dreier Bälle 2 Möglichkeiten zur Besetzung der vierten Stelle. Die fünfte Stelle ist automatisch festgelegt, da jeweils nur 1 Besetzungsmöglichkeit vorliegt. Insgesamt ergibt sich damit folgende Anzahl an Möglichkeiten:

    5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120

    Es gibt somit 120 verschiedene Möglichkeiten, die fünf Bälle der Reihe nach anzuordnen.

Permutationen mit nicht unterscheidbaren Objekten

Sind m von den insgesamt n Objekten nicht unterscheidbar, so können diese auf m! verschiedene Arten auf ihre Positionen verteilt werden. Da alle diese Möglichkeiten nur eine einzige Anordnung liefern, würden sie in der Permutations-Gleichung (1) fälschlicherweise zu einem m!-fachen an Kombinationsmöglichkeiten führen.

Um die Einschränkung an unterschiedlichen Anordnungen zu berücksichtigen, muss Gleichung (1) durch m! dividiert werden. Die Anzahl an n-Permutationen mit m identischen Objekten ist somit gleich \frac{n!}{m!}.

Sind allgemein jeweils m_1, m_2, \ldots der insgesamt n Objekte identisch, so lässt sich die Anzahl an Permutationen (unterschiedlichen Anordnungen) folgendermaßen berechnen:

(2)\frac{n}{m_1! \cdot m_2! \cdot \ldots}

Beispiele:

  • Auf wie viele verschiedene Arten lassen sich die Ziffern 001 anordnen?

    In diesem Fall treten zwei gleichartige Objekte (die zwei Nullen) auf. Für die Anzahl der möglichen Permutationen gilt somit:

    \frac{3!}{2!} = \frac{3 \cdot 2 \cdot 1}{2 \cdot 1} = 3

    Es sind somit drei verschiedene Permutationen (001 ,\, 010 ,\, 100) möglich.

  • Auf wie viele verschiedene Arten lassen sich die Buchstaben des Wortes „Mississippi“ anordnen?

Wären alle elf Buchstaben voneinander verschieden, so gäbe es 11! = 39\,916\,800 unterschiedliche Anordnungsmöglichkeiten. Von diesen Anordnungen sind allerdings 4! \cdot 4! \cdot 2! identisch, da es sich bei den vier Buchstaben „i“, den vier Buchstaben „s“ und den zwei Buchstaben „p“ um nicht unterscheidbare Objekte handelt, und die verschiedenen Anordnungsmöglichkeiten der gleichen Buchstaben jeweils zu nur einer einzigen zusammenfallen. Insgesamt ergibt sich somit folgende Anzahl an möglichen Anordnungen:

\frac{11!}{4! \cdot 4! \cdot 2!} = \frac{39\,916\,800}{1\ 152} = 34\,650

Es gibt also 34\,650 verschiedene Möglichkeiten, die elf Buchstaben unter Berücksichtigung der Reihenfolge anzuordnen.

Variationen

Bei einer Variation wird aus einer Menge von n-Elementen eine Auswahl an k Elementen entnommen; dabei wird die Reihenfolge der entnommenen Elemente berücksichtigt.

Variationen ohne Wiederholung

Wird aus einer Menge mit n Elementen eine Anzahl an k \le n Elementen entnommen, wobei kein Element mehrfach vorkommen darf, so ergibt sich (unter Berücksichtigung der Reihenfolge) eine bestimmte Anordnung der k Elemente. Mathematisch wird eine solche Anordnung (a_1,\, a_2,\, a_3,\, \ldots ,\, a_{\mathrm{k}}) als „Tupel“ bezeichnet.[1]

An der ersten Stelle des Tupels kann jedes der n Elemente auftreten. Für die Besetzung der zweiten Stelle sind nur noch (n-1) Möglichkeiten vorhanden, für die Besetzung der dritten Stelle (n-2) Möglichkeiten. Für die Besetzung k-ten Stelle gibt es schließlich (n-k+1) verschiedene Möglichkeiten. Die Anzahl an möglichen Tupeln ist somit insgesamt gleich:

(3)\frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)!

Da 0! = 1 gilt, kann im Fall k = n die obige Formel (3) als \frac{n!}{(n-n)!} = \frac{n!}{0!} = n! geschrieben werden. Dieser Fall entspricht somit einer Permutation der n Elemente beziehungsweise der Gleichung (1). Im Fall k < n wird die Produktreihe vorzeitig „abgeschnitten“.

Variationen mit Wiederholung

Wird aus einer Menge mit n Elementen eine Anzahl an k \le n Elementen entnommen, wobei jedes Element mehrfach vorkommen darf, so spricht man von einer Variation mit Wiederholung. Jedes Ergebnis ist wiederum ein Tupel (a_1,\, a_2,\, a_3,\, \ldots ,\, a_{\mathrm{k}}).

An jeder Stelle des Tupels kann, wenn eine Wiederholung der Elemente möglich ist, jedes der n Elemente auftreten. Die Anzahl an möglichen Tupeln ist somit gleich:

(4)\underbrace{n \cdot n \cdot n \cdot \ldots \cdot n}_{\text{$k$ mal} } = n^k

Beispiel:

  • Aus einer Liste mit 100 verschiedenen Zitaten wird jeden Tag nach einem Zufallsprinzip ein Zitat ausgewählt, um als „Zitat des Tages“ auf einer Homepage eingeblendet zu werden. Wie viele verschiedene Variationen der Zitate können in 7 Tagen auftreten?

    An jedem der Tage sind 10 verschiedene Zitate möglich, denn es kann auch an zwei oder mehreren aufeinander folgenden Tagen das gleiche Zitat erscheinen. Innerhalb einer Woche gilt damit für die Anzahl an möglichen Zitatefolgen:

    10 ^7 = 10\,000\,000

    Innerhalb einer Woche können somit zehn Millionen verschiedene Anordnungen der Zitate auftreten.

Kombinationen

Bei einer Kombination wird aus einer Menge von n-Elementen eine Auswahl an k Elementen entnommen; dabei wird die Reihenfolge der entnommenen Elemente nicht berücksichtigt.

Kombinationen ohne Wiederholung

Um k Elemente in einer bestimmten Reihenfolge aus einer Menge mit n Elementen auszuwählen, gibt es, wie im Abschnitt Variationen ohne Wiederholung besprochen, \frac{n!}{(n-k)!} Möglichkeiten. Hierbei wurde allerdings jede Reihenfolge der k Elemente als eigene Möglichkeit angesehen. Soll die Reihenfolge der entnommenen Elemente nicht berücksichtigt werden, so muss die Gesamtzahl \frac{n!}{(n-k)!} durch die Anzahl der möglichen Anordnungen der k Elemente dividiert werden (also durch k!).

Die sich ergebende Größe heißt Binomialkoeffizient und wird folgendermaßen dargestellt:

(5)\binom{n}{k} = \frac{n!}{(n - k)! \cdot k!}

Die Werte der Binomialkoeffizienten lassen sich als so genanntes „Pascalsches Dreieck“ anordnen. Da bei der Nummerierung der Zeilen und Spalten mit n=0 beziehungsweise k=0 begonnen wird, befindet sich der Koeffizient \binom{n}{k} in der (n+1)-ten Zeile an der (k+1)-ten Stelle.

fig-pascalsches-dreieck

Das Pascalsche Dreieck

SVG: Pascalsches Dreieck

Jede Zahl ist die Summe der beiden darüber liegenden Zahlen. Die Werte Binomialkoeefizienten können somit rekursiv nach folgender Formel berechnet werden:

\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}

Beispiel:

  • Wie viele Möglichkeiten gibt es, k=3 Kugeln aus einer Schale mit n=10 durchnummerierten Kugeln zu entnehmen, wenn die Reihenfolge keine Rolle spielt?

    Durch Einsetzen von k=3 und n=10 in Gleichung (5) erhält man:

    \binom{10}{3} = \frac{10!}{7! \cdot 3!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120

    Es gibt somit 120 verschiedene Möglichkeiten, aus zehn nummerierten Kugeln drei Stück auszuwählen.

Kombinationen mit Wiederholung

Wird aus einer Menge mit n Elementen eine Anzahl an k \le n Elementen entnommen, wobei jedes Element mehrfach vorkommen darf und die Reihenfolge der entnommenen Elemente nicht berücksichtigt wird, so spricht man von einer Kombination mit Wiederholung.[2] Hierfür gibt es folgende Anzahl an Möglichkeiten:

(6)\binom{n+k-1}{k} = \frac{(n + k -1)!}{(n-1)! \cdot k!}

Formal ist diese Formel mit der Binomialkoeffizienten-Gleichung (5) identisch, wenn man n durch den Wert (n+k-1) ersetzt.

Beispiel:

  • Wie viele Möglichkeiten gibt es bei einem k=3-fachen Werfen eines Würfels mit n=6 verschiedenen Seiten, wenn die Reihenfolge keine Rolle spielt?

    Durch Einsetzen von k=3 und n=6 in Gleichung (6) erhält man:

    \binom{6+3-1}{3} = \binom{8}{3} = \frac{8!}{5! \cdot 3!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56

    Es gibt bei dreimaligem Werfen des Würfels somit 56 verschiedene Kombinationen an erhaltenen Werten.

Anmerkungen:

[1]Auch geordnete Paare zweier Zahlen, beispielsweise die Koordinaten (x ,\, y) eines Punktes in einem zweidimensionalen Koordinatensystem, können somit als Tupel bezeichnet werden.
[2]Da jedes Element mehrfach vorkommen darf, ist bei Kombinationen mit Wiederholung auch k > n möglich.