Spielst Du auch manchmal verschiedene Computerspiele oder Spiele auf einer Spielekonsole? Stelle Dir vor, Du hast 5 verschiedene Spielekonsolen und willst sie alle nebeneinander auf Deinem Regal so richtig in Szene setzen. Was denkst Du, wie viele Möglichkeiten es gibt, diese aneinander zu stellen?
Die Anzahl an Möglichkeiten beschreibt die Anzahl an Permutationen bei einer Permutation ohne Wiederholung. Was das genau das ist, lernst Du im Folgenden.
Kombinatorik Grundlagenwissen – Permutationen
In der Kombinatorik begegnen Dir unzählige Fachbegriffe und Abzählmethoden. Darunter auch die sogenannte Permutation. Doch was genau steckt hinter diesem Begriff?
Permutation – Definition
Der Begriff "Permutation" ist abgeleitet von dem lateinischen Wort permutare und bedeutet "vertauschen", "umtauschen" oder "wechseln". In der Kombinatorik wird dies wie folgt definiert:
Als Permutation wird jede mögliche Anordnung von n verschiedenen Elementen aus einer Menge von insgesamt n Elementen bezeichnet.
Das Besondere ist hierbei, dass bei einer Permutation alle Elemente aus der Menge betrachtet werden und nicht nur eine Auswahl. Würde lediglich eine Stichprobe analysiert werden, dann fällt dies bereits in die Themenbereiche der Variation und Kombination. Diese unterscheiden sich dadurch, ob die Reihenfolge der gezogenen Elemente relevant ist oder nicht.
Damit Du das vorliegende Thema besser in die Gesamtthematik einsortieren kannst, ist im Folgenden ein kurzer Überblick dargestellt.
Abbildung 1: Überblick Abzählmethoden Kombinatorik
Mehr Informationen zu den einzelnen Themenbereichen kannst Du im Artikel zur Kombinatorik und den jeweiligen Unterkapiteln "Variation", "Kombination" und "Permutation mit Wiederholung" nachlesen.
Wie in der Einteilung in der obigen Abbildung zu sehen ist, lassen sich Permutationen noch einmal unterscheiden, und zwar in:
Was genau unterscheidet diese beiden Formen von Permutationen?
Permutationen – Unterscheidung
Je nachdem, ob alle n Elemente einer Menge von n Elementen voneinander unterscheidbar sind oder gewisse Elemente mehrmals vorkommen, lassen sich zwei Permutationen unterscheiden.
Zur besseren Übersicht sind in der Tabelle kurz die wesentlichen Unterschiede zwischen beiden Formen dargestellt.
Permutation mit Wiederholung | Permutation ohne Wiederholung |
Objekte sind nicht alle unterscheidbar bzw. können mehrfach vorkommen. | Objekte sind alle unterscheidbar bzw. sind jeweils nur einmal vorhanden. |
Menge von 3 Kugeln.  Abbildung 2: Doppelte blaue Kugeln
| Menge von 3 Kugeln.  Abbildung 3: Verschiedenfarbige Kugeln
|
Mehr Informationen und Inhalte zum Thema "Permutation mit Wiederholung" findest Du in der entsprechenden Erklärung.
Nachdem dieser kleinen Wiederholung zu den Abzählmethoden der Kombinatorik, kannst Du Dir direkt ansehen, was es mit Anordnungen von unterscheidbaren Elementen auf sich hat.
Permutation ohne Wiederholung – Erklärung
Wie Du bereits in der Definition von Permutationen und in der Tabelle gesehen hast, werden bei der Frage nach den Anordnungen immer alle verfügbaren Elemente (z. B. Kugeln in einer Urne) genutzt. Lediglich die Anzahl der mehrfach vorkommenden Elemente unterscheidet sich. Bei der Permutation ohne Wiederholung sind alle Elemente verschieden.
Eine Permutation ohne Wiederholung ist eine mögliche Anordnung von n Elementen einer Menge von n Elementen, wobei alle n Elemente unterschiedlich sind.
Elemente, wie Kugeln, können also in verschiedener Reihenfolge angeordnet werden. Jede dieser Anordnungen stellt eine Permutation dar.
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.
Ein weiteres Hilfsmittel zur Veranschaulichung der Anzahl von Anordnungen ist das sogenannte Baumdiagramm – zumindest bei einer geringen Anzahl von Elementen.
Permutation ohne Wiederholung – Baumdiagramm
Als Ereignisbaum oder Baumdiagramm wird die grafische Darstellung eines mehrstufigen Zufallsexperiments bezeichnet. Dieser Zufallsprozess lässt sich durch Zweige mit den verschiedenen Ereignissen verbinden.
Mehr Informationen zu Zufallsexperimenten und Ereignissen findest Du als Unterkapitel in der Kombinatorik.
Die Zweige bzw. Äste sind namensgebend für diese Art Diagramm. Am folgenden Beispiel zeigt sich, wie eine Darstellung mittels Baumdiagramm aussehen würde.
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.
Mit einem Baumdiagramm lassen sich auch Aussagen über Wahrscheinlichkeiten treffen. Dazu benötigst Du die Pfadregeln.
Mehr Informationen dazu findest Du in einer eigenen Erklärung zum Thema Baumdiagramm.
Du hast jetzt das Baumdiagramm als grafische Darstellungsmöglichkeit kennengelernt, aber wie genau definiert sich eine Permutation ohne Wiederholung?
Permutation ohne Wiederholung – Regeln
Damit Du bei einer gegebenen Situation einschätzen kannst, ob es sich um eine Permutation ohne Wiederholung handelt, hilft Dir hier eine kurze Zusammenfassung der Voraussetzungen dafür.
Anordnung von allen n Elementen einer Menge aus n Elementen.
Alle n Elemente der Menge müssen unterscheidbar sein.
Kein Element darf mehrfach verwendet werden.
Beachten der Reihenfolge der n Elemente.
Mit den oben genannten Merkmalen kannst Du einfach erkennen, wann es sich um eine Permutation ohne Wiederholung handelt.
Bei einer Menge von 3 Elementen lassen sich die Permutationen noch übersichtlich anhand eines Baumdiagramms oder dem Zeichnen der Anordnungen ermitteln. Was aber, wenn Du 10 oder 100 Elemente gegeben hast? Besteht eine Möglichkeit, dies einfach rechnerisch herauszufinden? Ja, die gibt es und zwar:
Permutation ohne Wiederholung – Formel
Berechnen lässt sich die Anzahl an Permutationen n Elementen durch die Fakultät der n Elemente.
Die Fakultät ist das Produkt einer Reihe von natürlichen Zahlen von 1 bis n. Die abgekürzte Schreibweise ist: \(n!\).
Wie viele Permutationen es bei einem Experiment gibt, kann demnach ohne viel Zeichenaufwand mathematisch berechnet werden.
Die Anzahl an Permutationen \(P(n)\) bei einer Permutation ohne Wiederholung mit einer Menge von \(n\) Elementen berechnet sich aus:
\(P(n)=n!\)
Was genau verbirgt sich hinter dem Ausdruck? Du hast die Möglichkeit, diesen Ausdruck direkt in den Taschenrechner einzugeben. Vielleicht hast Du diesen aber nicht immer zur Hand. Daher kannst Du stattdessen auch händisch die Anzahl der Permutationen berechnen.
Anzahl der Permutationen \(P(n)\) bei einer Permutation ohne Wiederholung mit einer Menge von \(n\) Elementen:
\[P(n)=n\cdot(n-1)\cdot(n-2)\cdot \dots\cdot 1=n!\]
Damit berechnest Du die Zahl der Anordnungsmöglichkeiten für alle unterschiedlichen Elemente. Sieh Dir dazu das folgende Rechenbeispiel an:
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.
Permutation ohne Wiederholung – Erklärung und Herleitung Formel
Jetzt weißt Du, was hinter diesem Ausrufezeichen steckt. Damit Du nachvollziehen kannst, wie die Fakultät zustande kommt, kannst Du Dir die Herleitung anhand des Kugel-Beispiels ansehen.
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\)
Permutation ohne Wiederholung – Anwendung und Beweis der Formel
Zu Beginn war die Frage offen, wie viele Platzierungsmöglichkeiten der 5 Spielekonsolen auf dem Regal bestehen. Die Anordnungen kannst Du natürlich durch Ausprobieren ermitteln. Möglich ist aber auch die Berechnung über die Formel.
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}
Natürlich kannst Du auch direkt die Fakultät über den Taschenrechner berechnen und Dir die Herleitung sparen.
Wie Du siehst, kannst Du Deine 5 Spielekonsolen auf \(120\) verschiedenen Möglichkeiten anordnen.
Erklärungen 
Magazine 
