Permutationen Beispiel Essay

Unter einer Permutation (von lateinischpermutare ‚vertauschen‘) versteht man in der Kombinatorik eine Anordnung von Objekten in einer bestimmten Reihenfolge. Je nachdem, ob manche Objekte mehrfach auftreten dürfen oder nicht, spricht man von einer Permutation mit Wiederholung oder einer Permutation ohne Wiederholung. Die Anzahl der Permutationen ohne Wiederholung ergibt sich als Fakultät, während die Anzahl der Permutationen mit Wiederholung über Multinomialkoeffizienten angegeben wird.

In der Gruppentheorie ist eine Permutation ohne Wiederholung eine bijektiveSelbstabbildung einer in der Regel endlichen Menge, wobei als Referenzmengen meist die ersten natürlichen Zahlen verwendet werden. Die Menge der Permutationen der ersten natürlichen Zahlen bildet mit der Hintereinanderausführung als Verknüpfung die symmetrische Gruppe vom Grad . Das neutrale Element dieser Gruppe stellt die identische Permutation dar, während das inverse Element die inverse Permutation ist. Die Untergruppen der symmetrischen Gruppe sind die Permutationsgruppen.

Wichtige Kenngrößen von Permutationen sind ihr Zykeltyp, ihre Ordnung und ihr Vorzeichen. Mit Hilfe der Fehlstände einer Permutation lässt sich auf der Menge der Permutationen fester Länge eine partielle Ordnung definieren. Über ihre Inversionstafel kann zudem jeder Permutation eine eindeutige Nummer in einem fakultätsbasierten Zahlensystem zugeordnet werden. Wichtige Klassen von Permutationen sind zyklische, fixpunktfreie, selbstinverse und alternierende Permutationen.

Permutationen besitzen vielfältige Einsatzbereiche innerhalb und außerhalb der Mathematik, beispielsweise in der linearen Algebra (Leibniz-Formel), der Analysis (Umordnung von Reihen), der Graphentheorie und Spieltheorie, der Kryptographie (Verschlüsselungsverfahren), der Informatik (Sortierverfahren) und der Quantenmechanik (Pauli-Prinzip).

Kombinatorische Grundlagen[Bearbeiten | Quelltext bearbeiten]

Problemstellung[Bearbeiten | Quelltext bearbeiten]

Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Beispiele für Permutationen sind:

  • Ein Anagramm ist eine Permutation der Buchstaben eines Wortes, wie beispielsweise ENKEL und NELKE.
  • Das Mischen der Karten eines Kartenspiels ist (im Idealfall) eine zufällige Permutation der Karten.
  • Im Volleyball ist der Stellungswechsel nach Eroberung des Aufschlagsrechts eine zyklische Permutation der Spieler.
  • Viele Sortierverfahren arbeiten mit sukzessiven Transpositionen, also Permutationen, die genau zwei Objekte vertauschen.

Werden in einer solchen Anordnung nicht alle Objekte ausgewählt, spricht man statt von einer Permutation von einer Variation, spielt die Reihenfolge bei der Auswahl keine Rolle, von einer Kombination. In der abzählenden Kombinatorik stellt sich nun die Frage nach der Anzahl möglicher Permutationen. Hierbei unterscheidet man den Fall, dass alle Objekte verschieden sind, von dem Fall, dass manche der Objekte identisch sind.

Permutation ohne Wiederholung[Bearbeiten | Quelltext bearbeiten]

Eine Permutation ohne Wiederholung ist eine Anordnung von Objekten, die alle unterscheidbar sind. Nachdem es für das erste Objekt Platzierungsmöglichkeiten gibt, kommen für das zweite Objekt nur noch Möglichkeiten in Betracht, für das dritte Objekt nur mehr und so weiter bis zum letzten Objekt, dem nur noch ein freier Platz bleibt. Die Anzahl der möglichen Permutationen von Objekten wird demnach durch die Fakultät

angegeben.

Beispielsweise gibt es mögliche Anordnungen von vier verschiedenfarbigen Kugeln in einer Reihe.

Permutation mit Wiederholung[Bearbeiten | Quelltext bearbeiten]

Eine Permutation mit Wiederholung ist eine Anordnung von Objekten, von denen manche nicht unterscheidbar sind. Sind genau Objekte identisch, dann sind diese auf ihren Plätzen vertauschbar, ohne dass sich dabei eine neue Reihenfolge ergibt. Auf diese Weise sind genau Anordnungen gleich. Die Anzahl der Permutationen von Objekten, von denen identisch sind, ist demnach durch die fallende Faktorielle

gegeben. Gibt es nicht nur eine, sondern Gruppen mit jeweils identischen Objekten, so können all diese Objekte auf ihren Plätzen vertauscht werden, ohne dass sich neue Anordnungen ergeben. Zählt man auch die Objekte, die nur einmal vorkommen, mit Vielfachheit , dann gilt und die Anzahl der möglichen Permutationen wird durch den Multinomialkoeffizienten

angeben.

Beispielsweise gibt es mögliche Anordnungen von vier farbigen Kugeln in einer Reihe, wenn genau zwei der Kugeln die gleiche Farbe aufweisen, und mögliche Anordnungen, wenn jeweils zwei Kugeln gleichfarbig sind.

Definition[Bearbeiten | Quelltext bearbeiten]

Sei eine Menge mit Elementen, dann ist eine -stellige Permutation (ohne Wiederholung) eine bijektive Abbildung

,

die jedem Element der Menge ein Element der gleichen Menge zuordnet. Anschaulich nimmt durch die Permutation jedes Element für den Platz des ihm zugeordneten Elements ein. Aufgrund der Bijektivität der Abbildung werden dabei zwei verschiedene Elemente niemals auf das gleiche Element abgebildet. Der Fall ist ebenfalls zugelassen und ist dann die leere Menge.

Da per Definition jede endliche Menge zu einer Menge der Form {1, 2, ..., n} gleichmächtig ist, kann man sich bei der mathematischen Betrachtung von Permutationen stets auf die ersten natürlichen Zahlen als Referenzmenge beschränken. Eine Permutation ist dann eine bijektive Abbildung

,

die jeder natürlichen Zahl zwischen und genau eine Zahl im gleichen Bereich zuordnet.[1] Stellt man sich alle Zahlen in einer Liste aneinandergereiht vor, dann nimmt die Zahl durch die Permutation den Platz mit der Nummer ein.

Notation[Bearbeiten | Quelltext bearbeiten]

Zweizeilenform[Bearbeiten | Quelltext bearbeiten]

In der ausführlichen Darstellung einer -stelligen Permutation schreibt man diese als Matrix mit zwei Zeilen und Spalten. In der oberen Zeile stehen die Zahlen von bis (in beliebiger Reihenfolge). Unter jeder Zahl steht dann in der zweiten Zeile der Funktionswert :

Auch in der zweiten Zeile steht somit jede Zahl von bis genau einmal.

Beispiel

Die Permutation mit und wird in der Zweizeilenform durch

notiert.

Tupelschreibweise[Bearbeiten | Quelltext bearbeiten]

Bei der kompakteren Tupelschreibweise schreibt man lediglich die Funktionswerte in eine Zeile:

Diese Schreibweise verwendet somit lediglich die zweite Zeile der Zweizeilenform. Da so die Information über die Zahl , die auf abgebildet wird, verloren geht, kann die Tupelschreibweise nur verwendet werden, wenn die Reihenfolge der Zahlen aus der ersten Zeile bekannt ist. In der Regel ist dies die natürliche Reihenfolge. Die Tupelschreibweise kann leicht mit der Zykelschreibweise (siehe folgenden Abschnitt) verwechselt werden, besonders da manche Autoren die Kommata weglassen.

Beispiel

Für die obige Beispielpermutation erhält man die Tupelschreibweise

.

Zykelschreibweise[Bearbeiten | Quelltext bearbeiten]

Die Zykelschreibweise benötigt ebenfalls nur eine Zeile. Man beginnt mit einer beliebigen Zahl und schreibt

,

wobei die -fache Hintereinanderausführung von bezeichnet und die kleinste natürliche Zahl mit ist. Eine solche Klammer heißt Zyklus und ist seine Länge. Gibt es weitere Zahlen, die noch nicht notiert wurden, so wählt man eine solche Zahl und schreibt einen weiteren Zyklus der Länge dahinter. Man fährt so lange fort, bis jede Zahl genau einmal notiert wurde. Klammern, in denen nur eine Zahl steht, können anschließend wieder gestrichen werden. Diese Darstellung ist nicht eindeutig, denn die Reihenfolge der Zyklen ist beliebig wählbar und in jedem Zyklus dürfen die Zahlen zyklisch vertauscht werden.

Beispiel

Für die obige Beispielpermutation verwendet man die folgenden Zykelschreibweisen:

Weitere Darstellungen[Bearbeiten | Quelltext bearbeiten]

Graphdarstellung[Bearbeiten | Quelltext bearbeiten]

Der Graph einer -stelligen Permutation ist ein gerichteter Graph mit Knotenmenge und Kantenmenge

.

In einem solchen Graphen besitzt jeder Knoten genau eine ausgehende und genau eine eingehende Kante. Die Zyklen des Graphen sind gerade die Zyklen der Permutation, wobei diejenigen Zahlen, die durch die Permutation festgehalten werden, Schleifen an den zugehörigen Knoten erzeugen. Der Graph einer Permutation ist nur dann zusammenhängend, wenn die Permutation aus einem einzelnen Zyklus der Länge

Alle sechs Permutationen dreier farbiger Kugeln
Permutationen vier farbiger Kugeln ohne Wiederholung (links) und mit Wiederholung (mitte und rechts).
Graph der Permutation

Eine fixpunktfreie Permutation oder Derangement (von französischdéranger „durcheinanderbringen“) ist in der Kombinatorik eine Permutation der Elemente einer Menge, sodass kein Element seine Ausgangsposition beibehält. Die Anzahl möglicher fixpunktfreier Permutationen einer Menge mit Elementen wird durch die Subfakultät angegeben. Für wachsendes strebt innerhalb der Menge der Permutationen von Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl. Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem partiellen Derangement, deren Anzahl durch die Rencontres-Zahlen ermittelt werden kann.

Ausgangsproblem[Bearbeiten | Quelltext bearbeiten]

Der französische Mathematiker Pierre Rémond de Montmort stellte Anfang des 18. Jahrhunderts in seinem Buch Essai d’analyse sur les jeux de hazard ein Spiel namens Treize („Dreizehn“) vor, das in vereinfachter Form wie folgt beschrieben werden kann:[1]

Ein Spieler mischt einen Satz von 13 Spielkarten einer Farbe und legt ihn als Stapel vor sich hin. Nun deckt er die Karten der Reihe nach auf, wobei er jede Karte gemäß der Reihenfolge As, Zwei, Drei bis König aufruft. Sollte irgendwann die aufgerufene Karte mit der aufgedeckten Karte übereinstimmen, so gewinnt er das Spiel; trifft dies bei keiner der 13 Karten zu, verliert er.

Nun stellt de Montmort sich die Frage nach der Wahrscheinlichkeit, mit der der Spieler das Spiel gewinnt. In der ersten Auflage seines Buchs von 1708 gibt de Montmort zwar das korrekte Ergebnis an, allerdings ohne genauere Herleitung. In der zweiten Auflage von 1713 stellt er dann zwei Beweise vor, einen eigenen, der auf einer rekursiven Darstellung beruht, und einen weiteren aus einem Briefwechsel mit Nikolaus Bernoulli, der auf dem Inklusions-Exklusions-Prinzip basiert. De Montmort zeigt weiter, dass die Gewinnwahrscheinlichkeit sehr nahe an dem Wert von liegt. Vermutlich stellt dies die erste Verwendung der Exponentialfunktion in der Wahrscheinlichkeitstheorie dar.[2]

Ohne die Vorarbeiten zu kennen analysierte Leonhard Euler 1753 ein verwandtes Glücksspiel namens Rencontre („Wiederkehr“), das folgendermaßen abläuft:[3]

Zwei Spieler besitzen jeweils ein vollständiges Kartenspiel mit 52 Karten. Sie mischen ihre Karten und legen diese als Stapel vor sich ab. Nun ziehen beide Spieler gleichzeitig immer wieder die oberste Karte von ihrem Stapel. Erscheint zu irgendeinem Zeitpunkt zweimal die gleiche Karte, so gewinnt der eine Spieler, andernfalls der andere.

Wiederum stellt sich die Frage nach der Gewinnwahrscheinlichkeit. Euler leitet die Lösung mit Hilfe weiterer Rekurrenzformeln her, wobei er annehmen darf, dass nur einer der Spieler seine Karten mischt und der andere Spieler seine Karten in einer vorgegebenen Reihenfolge aufdeckt. Weitere Varianten und Verallgemeinerungen der Fragestellung wurden unter anderem von de Moivre[4], Lambert[5] und Laplace[6] untersucht.

In modernen Lehrbüchern zur Kombinatorik wird das Problem häufig als „Problem der vertauschten Hüte“ (auch Mäntel, Koffer, Briefe oder ähnliches) in etwa so formuliert:[7][8][9]

Bei einem Empfang geben Gäste ihre Hüte an der Garderobe ab. Die Garderobenfrau ist an diesem Abend jedoch sehr zerstreut und gibt beim Verlassen jedem Gast einen zufällig gewählten Hut zurück. Wie groß ist die Wahrscheinlichkeit, dass mindestens ein Gast den richtigen Hut erhält?

Die drei mathematischen Probleme sind zueinander äquivalent und können durch das Studium fixpunktfreier Permutationen gelöst werden.

Definition[Bearbeiten | Quelltext bearbeiten]

Ist die symmetrische Gruppe aller Permutationen der Menge , dann heißt eine Permutation fixpunktfrei, wenn

für alle gilt. Eine fixpunktfreie Permutation ist damit eine Permutation, bei der kein Element seine Ausgangsposition beibehält, das heißt es tritt kein Zyklus der Länge eins auf. Bezeichnet die Menge aller fixpunktfreien Permutationen in und deren Anzahl, dann entspricht der Anteil

.

nach der Laplace-Formel gerade der Wahrscheinlichkeit für das Auftreten einer fixpunktfreien Permutation, wenn man annimmt, dass alle möglichen Permutationen in gleich wahrscheinlich sind. Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten natürlichen Zahlen beschränken.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Ein Fixpunkt einer Permutation ist dadurch charakterisiert, dass in ihrer Zweizeilenform zweimal die gleiche Zahl untereinander steht. Die einzige Permutation in

hat einen Fixpunkt und es gilt damit und . Die beiden Permutationen in sind

  und   ,

wobei die erste zwei Fixpunkte hat und die zweite keinen. Es gilt also und . Von den sechs Permutationen in

  und  

sind nur die vierte und fünfte fixpunktfrei, es gilt also und .

In besteht die Trägermenge aus der leeren Menge mit der einzigen Permutation darin, die leere Menge auf die leere Menge abzubilden. Da aus der leeren Menge kein Element ausgewählt werden kann, ist diese Permutation fixpunktfrei und es gilt und .

Anzahl[Bearbeiten | Quelltext bearbeiten]

fixpunktfreie
Permutationen
alle
Permutationen
Anteil
0 1 1 1
1 0 1 0
2 1 2 0,5
3 2 6 0,33333333...
4 9 24 0,375
5 44 120 0,36666666...
6 265 720 0,36805555...
7 1.854 5.040 0,36785714...
8 14.833 40.320 0,36788194...
9 133.496 362.880 0,36787918...
10 1.334.961 3.628.800 0,36787946...

Die Anzahl der fixpunktfreien Permutationen in lässt sich mit Hilfe der Subfakultät durch

  (Folge A000166 in OEIS)

ausdrücken. Der Anteil der fixpunktfreien Permutationen in ist entsprechend

.

Die Anzahl der fixpunktfreien Permutationen und ihr Anteil an der Gesamtzahl der Permutationen sind für bis in nebenstehender Tabelle zusammengefasst.

Für liegt damit der Anteil der fixpunktfreien Permutationen bei etwa 37 % (siehe auch 37%-Regel). Asymptotisch gilt für diesen Anteil

,

wobei die eulersche Zahl ist.

Herleitungen[Bearbeiten | Quelltext bearbeiten]

Herleitung über das Inklusions-Exklusions-Prinzip[Bearbeiten | Quelltext bearbeiten]

Bezeichnet

die Menge der Permutationen, die einen Fixpunkt an der Stelle aufweisen, dann hat die Menge der fixpunktfreien Permutationen die Darstellung

.

Damit ist die Anzahl der fixpunktfreien Permutationen durch

gegeben. Nach dem Prinzip von Inklusion und Exklusion gilt nun für die Mächtigkeit einer Vereinigungsmenge

Graph einer fixpunktfreien Permutation der Zahlen von 1 bis 8. Durch die Permutation wird keine der Zahlen festgehalten.
Die neun fixpunktfreien Permutationen von vier Elementen sind hervorgehoben
Categories: 1

0 Replies to “Permutationen Beispiel Essay”

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *