Permutation

aus Wikipedia, der freien Enzyklopädie

Unter einer Permutation (von lat. permutare „(ver)tauschen“) versteht man die Veränderung der Anordnung einer Menge durch Vertauschen ihrer Elemente. In der Mathematik ist eine Permutation eine bijektive Selbstabbildung einer in der Regel endlichen Menge. Umgangssprachlich findet der Begriff bisweilen auch als Synonym für „Anordnung“ Verwendung.

[Bearbeiten] Beispiele

„ANGSTBUDE“ entsteht aus „BUNDESTAG“ durch Permutation der Buchstaben (Anagramm). Damit man bei diesem Beispiel von einer Permutation sprechen kann, ist es wichtig, dass das Wort keinen Buchstaben mehr als einmal enthält.
Das Mischen der Karten eines Kartenspiels ist eine Permutation auf der Menge der Karten.
Der Stellungswechsel nach Eroberung des Aufschlagsrechts im Volleyball (rotieren) ist eine Permutation der Spieler.
Sortieralgorithmen wie zum Beispiel der Bubble Sort arbeiten mit sukzessivem Vertauschen, d. h. mit der Hintereinanderausführung von speziellen Permutationen, sogenannten Transpositionen (siehe unten).

[Bearbeiten] Permutationen in der Mathematik

[Bearbeiten] Definition

Eine $n$ -stellige Permutation ist eine bijektive Abbildung $\sigma : X_n \rightarrow X_n$ einer $n$ -elementigen Menge $X n$ auf sich selbst. Die $n$ -stelligen Permutationen bilden die Symmetrische Gruppe $S n$ mit $n!$ Elementen.

[Bearbeiten] Schreibweisen und Darstellungen

Es gibt im Wesentlichen drei Arten zur Beschreibung einer $n$ -stelligen Permutation: Die Matrixdarstellung, Zykelschreibweise und die Tupelschreibweise. Im Folgenden bezeichnen wir die $n$ Elemente von $X n$ mit $1,2,..., n$ und es sei $\sigma \in S_n$ .

[Bearbeiten] Matrixdarstellung

In der ausführlichen Darstellung der Permutation $σ$ schreibt man diese als $(2\times n)$ -Matrix. In der oberen Zeile stehen die Elemente von $X n$ (in beliebiger Reihenfolge). Ist $X n = {1,.., n}$ so verwendet man im Allgemeinen die Konvention die erste Zeile aufsteigend von $1$ bis $n$ zu schreiben, Unter jedes $x\in X_n$ schreibt man in die zweite Zeile den Funktionswert $σ(x)$ . Auch in der zweiten Zeile steht somit jedes Element von $X n$ genau einmal.

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

[Bearbeiten] Zykelschreibweise

Die Zykelschreibweise ist kompakter und benötigt nur eine Zeile. Wir beginnen mit einem beliebigen Element $a\in X_n$ und schreiben $(a \; \sigma(a) \; \sigma^2(a) \; \cdots \; \sigma^{|a|-1}(a))$ , wobei $| a |$ minimal ist mit $σ | a | (a) = a$ ( $| a |$ ist die Ordnung von $a$ ). Hierbei bezeichnet $σ k$ die $k$ -fache Hintereinanderausführung von $σ$ (siehe unten). Eine solche Klammer heißt ein Zykel und $| a |$ ist seine Länge. Gibt es weitere Elemente in $X n$ , die wir noch nicht notiert haben, so wählen wir ein solches Element $b$ und schreiben eine weitere Klammer $(b \; \sigma(b) \; \cdots \; \sigma^{|b|-1}(b))$ . Wir fahren so lange fort, bis wir jedes Element genau einmal notiert haben. Klammern, in denen nur ein Element steht, können anschließend wieder gestrichen werden. Die Identität notiert man auch als leere Klammer ().

(124)(35)

bedeutet beispielsweise, dass 1 auf 2, 2 auf 4 und 4 auf 1 abgebildet wird und zusätzlich 3 auf 5 und 5 auf 3.

[Bearbeiten] Tupelschreibweise

Die Tupelschreibweise ist festgelegt durch:

$\sigma = \left(\sigma\left(1\right),\sigma\left(2\right),\cdots,\sigma\left(n\right)\right)$

Sie wird leicht mit der Zykelschreibweise verwechselt, besonders da manche Autoren die Kommata weglassen.

[Bearbeiten] Darstellung mithilfe einer Permutationsmatrix

Diese Darstellung ist nicht zu verwechseln mit der Matrixdarstellung.

Bei dieser Darstellung wird ein Vektor von links mit einer Permutationsmatrix multipliziert, wodurch die Elemente des Vektors permutiert werden.

[Bearbeiten] Definition

Sei $X n = (x 1, x 2,..., x n)$ die $n$ -elementigen Menge und $P \in \mathbb{N}^{n\times n}$ die Permutationsmatrix.

Der Permutation $\sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \\ \sigma\left(x_1\right) & \sigma\left(x_2\right) & \cdots & \sigma\left(x_n\right) \end{pmatrix}$ entspricht dann die Matrix $P= \begin{pmatrix} p_{11} & \dots &p_{1n} \\ \vdots &\ddots &\vdots \\ p_{n1} & \dots &p_{nn} \end{pmatrix} = (p_{j,k})_{1\leqq j,k \leqq n}$ mit $p_{j,k}=\begin{cases} 1, & \text{wenn }\sigma(x_j)=x_k\text{ gilt } \\ 0, & \text{wenn } \sigma(x_j) \ne x_k\text{ gilt }\end{cases}$

Der Vektor $\overline{x} =\begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_n \\\end{pmatrix}$ wird nun Permutiert in dem man ihn von links mit $P$ multipliziert: $P \cdot \begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_n \\\end{pmatrix} = \begin{pmatrix} \sigma(x_1) \\ \sigma(x_2) \\ \vdots \\ \sigma(x_n) \\\end{pmatrix}$

[Bearbeiten] Bemerkung

Dabei ist die Einheitsmatrix $E_n = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}$ die identische Abbildung.

[Bearbeiten] Beispiele

Ein einfaches Beispiel in verschiedenen Schreibweisen: Es sei $\sigma_1 \colon \{a,b,c \} \rightarrow \{a,b,c \}$ durch $\sigma_1\left(a\right):=b, \sigma_1\left(b\right):=a \mbox{ und } \sigma_1\left(c\right):=c$ gegeben. Dann gilt

Matrixdarstellung:	$\sigma_1 = \begin{pmatrix} a & b & c \\ b & a & c \end{pmatrix}$
Zyklenschreibweise:	$\sigma_1 = \left(a b\right)\left(c\right) = \left(a b\right)$ – a und b werden vertauscht, c wird gehalten
Tupelschreibweise:	$\sigma_1 = \left(b,a,c\right)$ oder auch $\sigma_1 = \left(b\ a\ c\right)$
Permutationsmatrix:	$P \cdot \overline{x}= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix}a \\ b \\ c \\\end{pmatrix} = \begin{pmatrix}b \\ a \\ c \\\end{pmatrix}$ – a und b werden vertauscht, c wird gehalten

Ein weiteres Beispiel: Sei $\sigma_2 \in S_4$ durch $\sigma_2: 1, 2, 3, 4 \mapsto 4, 3, 2, 1$ gegeben. Dann schreibt man

Matrixdarstellung:	$\sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$
Zyklenschreibweise:	$\sigma_2 = \left(1\ 4\right)\left(2\ 3\right)$
Tupelschreibweise:	$\sigma_2 = \left(4,3,2,1\right)$ oder auch $\sigma_2 = \left(4\ 3\ 2\ 1\right)$
Permutationsmatrix:	$P \cdot \overline{x}= \begin{pmatrix} 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ \end{pmatrix} \cdot \begin{pmatrix}1 \\ 2 \\ 3 \\ 4 \\\end{pmatrix} = \begin{pmatrix}4 \\ 3 \\ 2 \\ 1 \\\end{pmatrix}$

Keine der Darstellungen ist eindeutig.

[Bearbeiten] Verknüpfung von Permutationen, Symmetrische Gruppe

Zwei $n$ -stellige Permutationen lassen sich nacheinander ausführen indem man die erste Permutation anwendet und auf deren Resultat dann die zweite Permutation. Diese Hintereinanderausführung wird auch Komposition, Verknüpfung oder Produkt zweier Permutationen genannt und ist selbst wieder eine $n$ -stellige Permutation.

Die Menge der $n$ -stelligen Permutationen bildet zusammen mit der Verknüpfung eine Gruppe: die Permutationsgruppe oder symmetrische Gruppe $S n$ . Ihr neutrales Element ist die Identität und zu jeder Permutation ist die inverse Permutation jeweils das inverse Element. Die symmetrischen Gruppen spielen in der Mathematik eine bedeutende Rolle. Beispielsweise ist jede endliche Gruppe zu einer Untergruppe einer symmetrischen Gruppe isomorph.

[Bearbeiten] Beispiele zur Komposition von Permutationen

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}$

Man beachte, dass die Verknüpfungen von rechts nach links ausgewertet werden (Manche Autoren werten jedoch auch von link nach rechts aus. [1]): 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)$

Die beiden letzten Beispiele zeigen, dass die Reihenfolge im Allgemeinen von Bedeutung ist: Die symmetrische Gruppe $S n$ ist für $n > 2$ nicht kommutativ. Die Reihenfolge kann nur unbeachtet bleiben, wenn die miteinander verknüpften Zykel disjunkt sind, d. h. jedes Element der Permutation kommt nur in einem Zykel vor. Beispiel:

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

$(132)\circ(45)= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4 \end{pmatrix} = (45) \circ(132)$

[Bearbeiten] Spezielle Permutationen

Identität: Die Identität (abgekürzt id) ist diejenige Permutation, die alle Elemente an ihrem Platz belässt.
Transposition oder 2-Zykel: Eine Transpositon ist eine Permutation, die genau zwei Elemente miteinander vertauscht.
Involution: Als Involution oder selbstinvers bezeichnet man eine Permutation $π$ , bei der bei zweifacher Anwendung alle Elemente an ihrem Platz bleiben. Formal bedeutet dies $π 2 = id$ . Eine Permutation ist genau dann eine Involution, wenn sie nur aus Fixpunkten und paarweise disjunkten Transpositionen besteht.
Fixpunkt: Ein Element, dessen Position sich bei der Permutation nicht ändert, nennt man einen Fixpunkt der Permutation. Bei der Permutation $(1,2,3,4) \mapsto (1,3,2,4)$ sind also genau 1 und 4 Fixpunkte. Man beachte den Unterschied in der Notation von Zykeln und Tupeln.
Derangement: Als Derangement bezeichnet man eine fixpunktfreie Permutation. Dies ist eine Permutation bei der kein einziges Element an seinem Platz bleibt.
Inverse Permutation: Zu jeder Permutation $π$ gibt es eine Permutation $π - 1$ mit $\pi \circ \pi^{-1} = \pi^{-1} \circ \pi = \mbox{id}$ . Man nennt $π - 1$ die zu $π$ inverse Permutation. Man erhält diese aus der Zyklendarstellung von $π$ , indem man das erste Element des Zyklus belässt und die restlichen Elemente umdreht, also in umgekehrter Reihenfolge aufschreibt.
Gerade Permutation: Eine Permutation heißt gerade, wenn sie Komposition einer geraden Anzahl von 2-Zykeln ist (siehe Signum und weiter unten).

[Bearbeiten] Einige Eigenschaften von Permutationen

Jede Permutation ist Komposition von 2-Zykeln.
Die Anzahl der Permutationen auf einer Menge mit n Elementen ist genau n!.
Ordnung: Für jede Permutation $π$ gibt es eine kleinste natürliche Zahl $k$ derart, dass $π k = id$ gilt. Also: Wendet man ein und die selbe Permutation oft genug an, so erhält man wieder die ursprüngliche Anordnung. $k$ ist hierbei das kleinste gemeinsame Vielfache (kgV) der Längen der Zyklen von $π$ und heißt die Ordnung der Permutation.

Besteht eine Permutation z. B. aus einem Zyklus der Länge 2 und einem Zyklus der Länge 3, so ist ihre Ordnung 6.
„left-to-right maximum“ (Links-Rechts Maximum, kurz: LR-Maximum). Bei einer Permutation in Wortschreibweise $a = a_1 \,\ldots a_i \ldots\, a_n$ nennt man $a i$ ein LR-Maximum, genau dann wenn $a i > a j$ mit $1 \leq j \leq i-1$ .

(Bemerkung: $a 1$ ist immer ein LR-Maximum).

Diese Eigenschaft ist von Nutzen, wenn man die normalisierte Zyklendarstellung ohne Klammern schreiben möchte. Man kann unter Ausnutzung der LR-Maxima zeigen, dass dann eine Bijektion zwischen der normalisierten Zyklendarstellung in eine Permutation existiert.^[1]
Inversion/Fehlstand: Man nennt ein Paar $(i, j)$ von Elementen Inversion bzgl. $π$ , falls gilt

$i < j$ und $\pi\left(i\right) > \pi\left(j\right)$ . Zwei Elemente bilden also genau dann eine Inversion, wenn nach Anwenden der Permutation das größere vor dem kleineren Element steht.

Beispiel: Gegeben sei die Permutation $32514$ . $1 < 2$ aber 2 steht hier vor 1 also 1,2 sind eine Inversion bezüglich $π$ .

Ordnet man in einer Tabelle jedem Element die Anzahl derjenigen Elemente zu, die nach der Permutation links von ihm stehen, obwohl sie größer sind, so erhält man die sogenannte Inversionstafel der Permutation. Umgekehrt kann man aus jeder solchen Tafel die Permutation eindeutig bestimmen.

Beispiel: Gegeben sei die Permutation $32514$ . Dann haben wir als Inversionstafel:

$\begin{pmatrix}1&2&3&4&5 \\ 3 & 1 & 0 & 1 & 0 \end{pmatrix}$

Signum: Sei mit $i\left(\pi\right)$ die Anzahl der Inversionen von $π$ bezeichnet. Dann ist das Signum von $π$ gegeben durch $\mathrm{sgn}\left(\pi\right) = \left(-1\right)^{i\left(\pi\right)}$ .

Eine Permutation hat also Signum 1, falls die Anzahl ihrer Inversionen gerade ist, ansonsten Signum −1.

Das Signum lässt sich auch über folgende Formel bestimmen:

$\mathrm{sgn}(\pi) = (-1)^{m_1+m_2+...+m_r+r},$

wobei $r$ die Anzahl der Zyklen und $m i$ die Länge des $i$ -ten Zyklus sind $\left(i=1,\ldots,r\right)$ .

Typ: Sei mit $b i$ die Anzahl der Zyklen von $π$ bezeichnet, welche die Länge $i$ haben. Dann ist der Typ einer Permutation der formale Ausdruck

$1^{b_1} 2^{b_2} 3^{b_3} \dots n^{b_n}$ .

Formal bedeutet hierbei, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden.

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

[Bearbeiten] Siehe auch

Permutiertes Register

[Bearbeiten] Weblink

Wiktionary: Permutation – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen und Grammatik

[Bearbeiten] Literatur

Albrecht Beutelspacher: Lineare Algebra. Kapitel 7.2 Permutationen, ISBN 3-528-56508-X.
Michael Artin: Algebra. Kapitel 1.4 Permutationsmatrizen, ISBN 3-7643-2927-0.

[Bearbeiten] Einzelnachweise

↑ Vorlesungsskript Prof. Welker: Kapitel 1 & Kapitel 3 (PDF)

Kategorien: Gruppentheorie | Kombinatorik | Lineare Algebra

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Permutation

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Beispiele

[Bearbeiten] Permutationen in der Mathematik

[Bearbeiten] Definition

[Bearbeiten] Schreibweisen und Darstellungen

[Bearbeiten] Matrixdarstellung

[Bearbeiten] Zykelschreibweise

[Bearbeiten] Tupelschreibweise

[Bearbeiten] Darstellung mithilfe einer Permutationsmatrix

[Bearbeiten] Definition

[Bearbeiten] Bemerkung

[Bearbeiten] Beispiele

[Bearbeiten] Verknüpfung von Permutationen, Symmetrische Gruppe

[Bearbeiten] Beispiele zur Komposition von Permutationen

[Bearbeiten] Spezielle Permutationen

[Bearbeiten] Einige Eigenschaften von Permutationen

[Bearbeiten] Siehe auch

[Bearbeiten] Weblink

[Bearbeiten] Literatur

[Bearbeiten] Einzelnachweise

Views

Navigation

Mitmachen

Suche

Andere Sprachen