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.