Permutationen Definition
Permutation Definition
- Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge. Man unterscheidet:
- Permutationen ohne Wiederholung: alle Objekte sind verschieden
- Permutationen mit Wiederholung: manche der Objekte sind nicht unterscheidbar Anzahlen
- Anzahlen:
- Zahl der Permutationen von $n$ Objekten ohne Wiederholung: $n! = 1 \cdot 2 \cdot ... \cdot n$
- Zahl der Permutationen von n Objekten, von denen k nicht unterscheidbar sind: $\frac{n!}{k!}$
- Zahl der Permutationen von $n$ Objekten, von denen $ k_1,...,k_s$ nicht unterscheidbar sind: $\frac{n!}{k_1! \cdot ... \cdot k_s!}$
- Notation
Gibt man jedem Objekt eine Nummer, dann kann eine Permutation ohne Wiederholung als Abbildung der Menge {1, . . . , n} in sich selbst angesehen werden, bei der jede Zahl genau einmal als Abbild vorkommt. Man schreibt: $ \pi : \left\{1, . . . , n\right\} \rightarrow \left\{1, . . . , n\right\} $ und gibt zudem die Abbildungsvorschrift an (explizit, Wertetabelle, Tupeldarstellung).
Hintereinanderausfuhrung
Zwei Permutationen $\pi$ und $\sigma$ können hintereinander ausgeführt werden. Man erhält dann eine neue Permutation, die dadurch entsteht, dass erst $\pi$ angewandt wird und auf das Ergebnis dann $\sigma$. Man notiert diese Permutation als $ \sigma \circ \pi$ (von rechts nach links zu lesen) mit der Abbildungsvorschrift $1 \mapsto \sigma(\pi(1)), 2 \mapsto \sigma(\pi(2)),..., n \mapsto \sigma(\pi(n))$.
Die Hintereinanderausfuhrung ist nicht kommutativ, das heißt im Allgemeinen gilt $\sigma \circ \pi \neq \pi \circ \sigma$.
Umkehrpermutation
Zu jeder Permutation $\pi$ gibt es eine Umkehrpermutation $\pi$, die die Vertauschung wieder rückgängig macht. Es gilt $$ \pi^{-1} \circ \pi = \pi \circ \pi^{-1} = id $$ wobei $id = (1, 2,..., n)$ die identische Permutation ist, die alle Zahlen an ihrem Platz lässt.
Kommentare
Weitere Lernmaterialien vom Autor 🦄
Top-Lernmaterialien aus der Community 🐬
Kombinatorik Erklärung mit Formeln, Beispielen und Aufgaben
Variationen Definition und Mengendarstellung
Satz von Bayes Definition und Beispiele