Permutation

Unter einer Permutation versteht man in der Mathematik die Veränderung der Reihenfolge der Elemente einer Menge.

Bei einem Kartenspiel sind zum Beispiel nach jedem Mischen die Karten anders sortiert. Dabei handelt es sich jedesmal um eine Permutation auf den Elementen (Karten) einer Menge (Kartenstapel).

Auch bei Wörtern oder Sätzen einer Sprache treten Vertauschungen auf: z.B. Bundestag - Angstbude. Diese bezeichnet man in der Linguistik als Anagramme. Sie sind jedoch nicht Gegenstand dieses Artikels.

Inhaltsverzeichnis

1 Definition

1.1 Kombinatorik
1.2 Gruppentheorie

2 Schreibweise

2.1 Abbildung
2.2 Matrixdarstellung
2.3 Vektordarstellung
2.4 Zyklenschreibweise

3 Beispiele

4 Spezialfälle

5 Eigenschaften

Definition

Die beiden folgenden Definitionen sind gleichwertig, d.h. jede der beiden Definitionen kann aus der jeweils anderen hergeleitet oder durch diese ersetzt werden.

Kombinatorik

In der Kombinatorik versteht man unter einer n-stelligen Permutation (bzw. einer n-stelligen Permutation ohne Wiederholung) die Anordnung einer Menge mit n Elementen. Beispielsweise sind ( c b a ) und ( b c a ) zwei unterschiedliche Permutationen der Menge { a, b, c }.

Die Anzahl aller Permutationen von n Elementen berechnet sich zu n!.

Gruppentheorie

In der Gruppentheorie versteht man unter einer n-stelligen Permutation die bijektive Abbildung $\sigma: X_{n} \rightarrow X_{n}$ einer Menge mit n Elementen auf sich selbst.

Mit der Verkettung als Verknüpfung bildet die Menge der n-stelligen Permutationen die Symmetrische Gruppe S_n. So lassen sich z.B. auch Drehung und Spiegelung von geometrischen Figuren als (verknüpfte) Permutationen ausdrücken.

Schreibweise

Da die "Namen" der Mengenelemente für die Definition einer Permutation nicht von Bedeutung sind, benutzt man als Mengenelemente häufig die Zahlen von 1 bis n als "Namen".

Abbildung

$\sigma: \lbrace 1, ..., n \rbrace \rightarrow \lbrace \sigma\left(1\right), ..., \sigma\left(n\right)\rbrace$

Matrixdarstellung

In der ausführlichen Darstellung einer Permutation schreibt man diese als zweizeilige Matrix, in jeder Spalte der Matrix steht unter einer Zahl deren Funktionswert.

$\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma\left(1\right) & \sigma\left(2\right) & \cdots & \sigma\left(n\right) \end{pmatrix}$

Vektordarstellung

Die Vektordarstellung ist ein Spezialfall der Matrixdarstellung. Da die Reihenfolge der einzelnen Spalten einer Matrix für die Abbildung ohne Bedeutung ist, kann man diese beliebig vertauschen, ohne dass sich dabei die Permutation selbst verändert. Man ordnet nun die Spalten so, dass in der obersten Zeile die Elemente in aufsteigender Folge dargestellt werden. Die obere Zeile enthält nun keine praktische Information mehr und kann deshalb in einer verkürzten Darstellung einfach weggelassen werden.

$\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma\left(1\right) & \sigma\left(2\right) & \cdots & \sigma\left(n\right) \end{pmatrix} = \begin{pmatrix} \sigma\left(1\right) & \sigma\left(2\right) & \cdots & \sigma\left(n\right) \end{pmatrix}$

Zyklenschreibweise

Jede Permutation lässt sich als Produkt elementefremder Zyklen darstellen. Diese Darstellung ist viel übersichtlicher und viele Eigenschaften der Permutation können direkt abgelesen werden. Die genaue Schreibweise ist aus den Beispielen ersichtlich.

Beispiele

Ein einfaches Beispiel in den vier Schreibweisen:

$\sigma_1: \lbrace a, b, c \rbrace \rightarrow \lbrace b, a, c \rbrace$
$\sigma_1 = \begin{pmatrix} a & b & c \\ b & a & c \end{pmatrix}$
$σ 1 = (b a c)$
$σ 1 = (a b)(c) = (a b)$ - a und b werden vertauscht, c wird gehalten

Ein weiteres Beispiel in den vier Schreibweisen:

$\sigma_2: \lbrace 1, 2, 3, 4 \rbrace \rightarrow \lbrace 4, 3, 2, 1 \rbrace$
$\sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$
$σ 2 = (4321)$
$σ 2 = (14)(23)$

Beispiele zur Verknüpfung:

$\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$

Erklärung: In der zweiten Matrix geht die 1 in die 1, in der ersten die 1 in die 3. Im Ergebnis der Verknüpfung geht also die 1 in die 3. Ebenso: zweite Matrix 2 -> 3, erste Matrix 3 -> 2, Ergebnis 2 -> 2. Und: zweite Matrix 3 -> 2, erste Matrix 2 -> 1, Ergebnis 3 -> 1.

$(132)\circ(23)=(1 3)$
$(23)\circ(132)=(1 2)$

Vergleiche mit vorherigem Beispiel: Man sieht, die Verknüpfung ist nicht kommutativ.

Spezialfälle

Identität, zum Beispiel: $(1)$ , $\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$ .
Transposition
Derangement

Eigenschaften

Auf die Eigenschaften der Permutation und der Verkettung wird bei der Symmetrischen Gruppe eingegangen.

20px|Wiktionary Wiktionary: Weiteres zur Wortherkunft, Synonyme und Übersetzungen von Permutation