Permutation

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?

Beispiel

Wir haben drei mit den Zahlen 1, 2 und 3 nummerierte 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: 3 ! (das ! steht für Fakultät) = 3 × 2 × 1 = 6.

Bei 4 Kugeln gäbe es 4 ! Möglichkeiten der Anordnung, d.h. 4 × 3 × 2 × 1 = 24; bei 5 Kugeln dann 5 ! = 120 Möglichkeiten u.s.w.

Bei der Permutation wird 1) mit allen Elementen (im Beispiel 3 Kugeln) gearbeitet, diese werden 2) (zumindest gedanklich) so oft wie möglich vertauscht (lateinisch permutare: tauschen) und 3) die Reihenfolge ist wichtig. Es wird keine Auswahl getroffen (z.B. 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 / ohne Wiederholung

Permutation ohne Wiederholung

In dem obigen Beispiel waren alle 3 Kugeln durch die Nummerierung eindeutig unterscheidbar und dieses Modell wird als "Permutation ohne Wiederholung" bezeichnet und wie oben als Fakultät der Anzahl der Elemente berechnet.

Permutation mit Wiederholung

Beispiel: Permutation mit Wiederholung

Wären die Kugeln in dem obigen Beispiel nicht eindeutig unterscheidbar, sondern wären z.B. 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

Als Formel: 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.