Skip to content Skip to navigation

Permutationen

Permutation Definition

Hintereinanderausführung

Umkehrpermutation

 

 

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.

Beliebte Inhalte auf Schulminator