Permutation ohne Wiederholung

Stelle Dir vor, es liegen 3 verschiedenfarbige Kugeln/Murmeln (Elemente) vor Dir. Würdest Du diese der Reihe nach anordnen, so gäbe es dazu unterschiedliche Möglichkeiten. Probiere es gern direkt mit aus.

Abbildung 4: Beispiel mit Kugeln

An erster Stelle könntest Du sowohl mit der blauen Kugel beginnen oder auch mit der orangen oder türkisen. Die Kugeln lassen sich wie folgt in verschiedenen Reihenfolgen anordnen und sortieren:

Abbildung 5: Angeordnete Kugeln

Wie Du sehen kannst, spielt es eine entscheidende Rolle, in welcher Reihenfolge die Kugeln arrangiert werden. So ergeben sich für \(n=3\) verschiedenfarbige Kugeln insgesamt 6 verschiedene Permutationen.

Das Zufallsexperiment des Ziehens von Kugeln aus einer Urne lässt sich anhand des Ereignisbaums darstellen.

Es gibt wieder eine Gesamtmenge von 3 Kugeln, wobei alle 3 Kugeln unterschiedlich sind. Eine blaue Kugel, eine orange Kugel und eine türkise Kugel.

In der 1. Stufe des Zufallsexperiments wird eine Kugel gezogen. Diese kann blau, orange oder türkis sein. Daher müssen an der Wurzel des Baumdiagramms drei Zweige eingezeichnet werden.

Abbildung 6: Stufe 1 Baumdiagramm

Wurde beim 1. Zug bereits eine blaue Kugel gezogen, so ist beim 2. Zug natürlich nur noch das Ziehen einer orangen oder türkisfarbenen Kugel möglich. Ebenso verhält es sich bei den beiden anderen Möglichkeiten, der orangen und türkisfarbenen Kugel.

Es gibt jeweils nur zwei weitere Auswahlmöglichkeiten. Daher kann das Baumdiagramm in der 2. Stufe um zwei Zweige erweitert werden.

Abbildung 7: Stufe 2 Baumdiagramm

In der letzten und 3. Stufe des Zufallsexperiments wird die letzte verbleibende Kugel aus der Urne gezogen. Je nach Zweig kann das entweder die blaue, die orange oder die türkisfarbene Kugel sein. So kann das Baumdiagramm mit allen 3 Zügen vervollständigt werden.

Abbildung 8: Stufe 3 Baumdiagramm

Der Ereignisbaum bzw. das Baumdiagramm des Zufallsexperiments ist damit fertig. Doch wie lassen sich dort die möglichen Permutationen auslesen? Das ist möglich, indem der Pfad entlang des Baumdiagramms verfolgt wird, wie beispielhaft in Abbildung 9 die türkise Markierung zeigt.

Abbildung 9: Pfad entlang des Baumdiagramms

Der türkise Pfad zeigt hier etwa die Anordnung (Permutation) blau, orange und türkis.

Abbildung 10: Mögliche Permutation am Baumdiagramm

Verfolgst Du nun alle Pfade im Baumdiagramm, so erhältst Du folgende Permutationen in diesem Beispiel:

Abbildung 11: Permutationen des Beispiels

Sieh Dir im Vergleich dazu einmal die Permutationen aus Abbildungen 5 des obigen Beispiels an. Es sind dieselben 6 Permutationen. Entlang der Pfade eines Baumdiagramms können demnach ebenfalls die Permutationen bestimmt werden.

Aufgabe 1

Berechne die Anzahl der Permutationen ohne Taschenrechner für eine Menge von \(n=4\) verschiedenen Objekten.

Lösung

Mithilfe der obigen Formel kannst Du die Anzahl der Permutationen \(P(n)\) errechnen.\begin{align}P(n)&=n!\\P(4)&=4!\end{align} Ohne Taschenrechner muss die Fakultät in ihre Einzelteile aufgegliedert werden. Das erfolgt durch das Multiplizieren der einzelnen Komponenten. Begonnen wird mit der Zahl 4. Diese wird um 1 verringert, so erhältst Du die 3. Noch einmal verringert um 1 ergibt sich 2. Ein letztes Mal verringert erhältst Du 1.\begin{align}P(n)&=n\cdot(n-1)\cdot(n-2)\cdot \dots\cdot 1\\P(4)&=4\cdot 3\cdot 2\cdot 1\\&=24\end{align}

So kannst Du die Berechnung der Fakultät auch ohne Taschenrechner ausführen.

Stelle Dir vor, Du müsstest 3 Murmeln bzw. Kugeln zurück in eine dafür vorgesehene Schachtel legen und hättest dabei 3 freie Plätze.

Abbildung 12: Platzierungsmöglichkeiten

Zunächst möchtest Du am 1. Platz eine Murmel zurücklegen. Wie viele Möglichkeiten hast Du dabei? Bisher gibt es noch eine freie Auswahl der Murmeln, denn aktuell hast Du noch alle 3 Murmeln zur Verfügung. Du kannst also an Platz 1 jede von den 3 Kugeln hinlegen. Es gibt demnach n Möglichkeiten.

Platz 1: \(n\)

Abbildung 13: Platzierung an Platz 1

Ist die 1. Kugel platziert, so steht für den 2. Platz lediglich die Auswahl von 2 verschiedenen Kugeln zur Verfügung, denn die 1. Kugel wurde bereits platziert. Ist an Platz 1 etwa die blaue Kugel platziert worden, so besteht noch die Wahl zwischen oranger und türkisfarbener Kugel.

Es gibt demnach nicht mehr \(n=3\) Möglichkeiten, sondern nur noch 2, also \((n-1)\).

Platz 2: \(n-1\)

Abbildung 14: Platzierung an Platz 2

Nun ist nur noch der letzte Platz übrig. Wird an Platz 2 die orange Kugel festgelegt, siehst Du, dass für Platz 3 keine Auswahlmöglichkeit mehr besteht. Es kann nur noch die türkisfarbene Murmel an diesem Platz platziert werden.

Platz 3: \(n-2=1\)

Abbildung 15: Platzierung an Platz 3

Um die Anzahl der Permutationen für die Plätze zu ermitteln, müssen die verschiedenen Möglichkeiten der 3 Plätze miteinander multipliziert werden.

\(P(n)=3! = 3\cdot 2\cdot 1\)

Aufgabe 2

Wie viele Platzierungsmöglichkeiten auf dem Regal ergeben sich bei 5 verschiedenen Spielekonsolen?

Lösung

Du hast 5 Spielekonsolen, also \(n=5\) Elemente. Für die erste Konsole kannst Du ganz frei entscheiden, wo sie stehen soll. Es sind n mögliche Plätze vorhanden (also alle). Für die zweite Konsole steht jetzt ein Platz weniger zur Verfügung, weil Du die erste schon hingestellt hast.

Platz 2: (n-1)

Für die dritte Konsole sind schon zwei Plätze weniger zur Verfügung, weil Du bereits zwei Spielekonsolen aufgestellt hast:

Platz 3: (n-2)

Für die vierte Konsole gilt daher:

Platz 4: (n-3)

Für die fünfte Konsole gilt:

Platz 5: (n-4) = 1

Mit dem oben genannten allgemeinen Zählprinzip ergibt sich also Folgendes:

\begin{align} P(n) &= n!\\P(5) &= 5!\\&= 5\cdot 4\cdot 3\cdot 2\cdot 1\\&=120\end{align}

Wie Du siehst, kannst Du Deine 5 Spielekonsolen auf \(120\) verschiedenen Möglichkeiten anordnen.