Permutation

Definition

Permutationen im Rahmen der Kombinatorik sind Anordnungen von einer bestimmten Anzahl von Elementen in einer bestimmten Reihenfolge.

Die Reihenfolge ist bei Permutationen – im Gegensatz zu Kombinationen – immer von Bedeutung.

Als Fragestellung:

Auf wieviele Arten kann man die Elemente anordnen?

Permutation ohne Wiederholung

Sind die Elemente eindeutig unterscheidbar, wird dieses Modell als "Permutation ohne Wiederholung" bezeichnet.

Beispiel

Wir haben n = 3 mit den Zahlen 1, 2 und 3 nummerierte und damit eindeutig unterscheidbare Kugeln.

Wie viele Möglichkeiten gibt es, diese anzuordnen?

Man kann die Möglichkeiten abzählen:

  • 1 2 3
  • 1 3 2
  • 2 1 3
  • 2 3 1
  • 3 1 2
  • 3 2 1

Das sind 6 Möglichkeiten.

Einfacher geht es mit einer Formel: n! (das ! steht für Fakultät, Funktion auf dem Taschenrechner verfügbar).

Für die 3 Kugeln:

3! = 3 × 2 × 1 = 6.

Bei 4 Kugeln gäbe es 4! Möglichkeiten der Anordnung, das heißt 4 × 3 × 2 × 1 = 24; bei 5 Kugeln dann 5! = 120 Möglichkeiten und so weiter.

Das "Wesen" der Permutation – Merkmale und Abgrenzung

Bei der Permutation wird

  1. mit allen Elementen (im Beispiel 3 Kugeln) gearbeitet,
  2. diese werden (zumindest gedanklich) so oft wie möglich vertauscht (lateinisch permutare: tauschen) und
  3. die Reihenfolge ist wichtig.

Es wird keine Auswahl getroffen (zum Beispiel 2 aus 3 oder 6 aus 49; das wären Variationen (wenn es auf die Reihenfolge ankommt) bzw. Kombinationen (wenn die Reihenfolge egal ist wie beim Lotto)).

Permutation mit Wiederholung

Sind die Elemente nicht alle eindeutig unterscheidbar, bezeichnet man dieses Modell als "Permutation mit Wiederholung".

Beispiel

Wären die Kugeln in dem obigen Beispiel nicht eindeutig unterscheidbar, sondern wären zum Beispiel 2 Kugeln schwarz und eine Kugel weiß, bezeichnet man dieses Modell als "Permutation mit Wiederholung".

Wie viele Möglichkeiten gibt es, diese anzuordnen?

Man kann die Möglichkeiten wieder abzählen:

  • schwarz schwarz weiß
  • schwarz weiß schwarz
  • weiß schwarz schwarz

Mit einer Formel:

$$\frac{n!}{k_1! \cdot k_2! \dots k_n!)}$$

Dabei ist

  • n die Anzahl der Kugeln
  • $k_1$, $k_2$ bis zu $k_n$ sind die jeweilige Häufigkeit der unterscheidbaren Elemente (hier ist $k_1$ die Anzahl der schwarzen Kugeln (2) und $k_2$ ist die Anzahl der weißen Kugeln (1) und mehr gibt es hier nicht).

Für das Beispiel:

3! / (2! × 1!) = 6 / 2 = 3 (Möglichkeiten der Anordnung).

Dabei ist 3 die Anzahl der Kugeln, 2 die Anzahl der schwarzen Kugeln und 1 die Anzahl der weißen Kugeln.