Permutation


Permutation
Permutationen dreier Kugeln

Unter einer Permutation (von lateinisch 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.

Inhaltsverzeichnis

Beispiele

  • „ANGSTBUDE“ entsteht aus „BUNDESTAG“ durch Permutation der Buchstaben (Anagramm).
  • 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).

Formale Definition

Eine n-stellige Permutation ist eine bijektive Abbildung \sigma : X_n \rightarrow X_n einer n-elementigen Menge Xn auf sich selbst. Für eine n-elementige Menge gibt es jeweils n! mögliche Permutationen.

Die n-stelligen Permutationen der ersten n natürlichen Zahlen 1, 2, 3, \ldots, n bilden mit der Komposition von Abbildungen als Verknüpfung die symmetrische Gruppe Sn (mit n! Elementen). Für die symmetrische Gruppe einer beliebigen Menge Xn schreibt man allgemein S(Xn). Ihr neutrales Element ist die Identität (abgekürzt id), also diejenige Permutation, die alle Elemente an ihrem Platz belässt. Zu jeder Permutation σ gibt es genau eine inverse Permutation σ − 1 mit \sigma \circ  \sigma^{-1} = \sigma^{-1} \circ \sigma = \mathrm{id}.

Die symmetrischen Gruppen spielen in der Mathematik eine bedeutende Rolle. Beispielsweise ist nach dem Satz von Cayley jede endliche Gruppe zu einer Untergruppe einer symmetrischen Gruppe isomorph.

Mathematische Schreibweisen und Darstellungen

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

Matrixdarstellung

In der ausführlichen Darstellung der Permutation σ schreibt man diese als (2\times n)-Matrix. In der oberen Zeile stehen die Elemente von Xn (in beliebiger Reihenfolge). Ist Xn = {1,..,n}, dann schreibt man im Allgemeinen die Zahlen von 1 bis n nacheinander in die erste Zeile. 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 Xn genau einmal.

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

Zykelschreibweise

Die Zykelschreibweise ist kompakter und benötigt nur eine Zeile. Man beginnt mit einem beliebigen Element a\in X_n und schreibt

\left(a \; \sigma(a) \; \sigma^2(a) \; \cdots \; \sigma^{\ell_a-1}(a)\right),

wobei σk die k-fache Hintereinanderausführung von σ bezeichnet und \ell_a die kleinste natürliche Zahl mit \sigma^{\ell_a}(a) = a ist. Eine solche Klammer heißt ein Zykel und \ell_a ist seine Länge. Gibt es weitere Elemente in Xn, die noch nicht notiert wurden, so wählt man ein solches Element b und schreibt einen weiteren Zykel \left(b \; \sigma(b) \; \cdots \; \sigma^{\ell_b-1}(b)\right) der Länge \ell_b. Man fährt so lange fort, bis jedes Element genau einmal notiert wurde. Klammern, in denen nur ein Element steht, können anschließend wieder gestrichen werden. Diese Darstellung ist nicht eindeutig: Die Reihenfolge der Zykel ist beliebig wählbar und in jedem Zykel dürfen die Elemente zyklisch vertauscht werden. Die Identität id notiert man auch als leere Klammer (), als (1) oder als \epsilon. Die inverse Permutation erhält man, indem man in der Zykelschreibweise in jedem Zykel die Elemente in der umgekehrten Reihenfolge schreibt.

σ = (124)(35) bedeutet beispielsweise, dass σ 1 auf 2, 2 auf 4 und 4 auf 1 abbildet und zusätzlich 3 auf 5 und 5 auf 3. Es gilt σ − 1 = (421)(53) = (142)(35).

Eine Permutation, die r Elemente zyklisch vertauscht und die übrigen Elemente fest lässt, wird in dieser Notation als ein einzelner Zykel der Länge r geschrieben und r-Zykel genannt. Ein 2-Zykel, also eine Vertauschung zweier Elemente, heißt auch Transposition. Jeder Zykel und damit auch jede Permutation lässt sich als Komposition von Transpositionen schreiben.

Tupelschreibweise

Bei der Tupelschreibweise schreibt man die Funktionswerte σ(x) in eine Zeile.

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

Sie enthält somit nur noch die zweite Zeile der Matrixdarstellung. Da dadurch die Information über den x-Wert zu den σ(x) verloren geht, kann die Tupelschreibweise nur verwendet werden, wenn für die zugrundeliegende Menge eine Reihenfolge festgelegt wurde. Anhand dieser Reihenfolge lässt sich dann die erste Zeile der Matrixdarstellung rekonstruieren.

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

Permutationsmatrix

Matrizen der Permutationen dreier Elemente

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.

Definition

Sei X_n=(x_1,x_2,\ldots,x_n) das n-Tupel und P_\sigma \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_\sigma=
  \begin{pmatrix}
    p_{11} & \dots &p_{1n} \\
    \vdots &\ddots &\vdots \\
    p_{n1} & \dots &p_{nn}
  \end{pmatrix}
  = (p_{j,k})_{1\leq j,k \leq n} \quad\text{ mit }\quad 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 permutiert, indem man ihn von links mit Pσ multipliziert: P_\sigma \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}

Bemerkung

Die identische Abbildung wird dargestellt durch die Einheitsmatrix .

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}
Zykelschreibweise: \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 \colon \{1, 2, 3, 4 \} \rightarrow \{1, 2, 3, 4 \} durch \sigma_2\left(1\right):=4, \sigma_2\left(2\right):=3, \sigma_2\left(3\right):=2 \mbox{ und } \sigma_2\left(4\right):=1 gegeben. Dann schreibt man
Matrixdarstellung: \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}
Zykelschreibweise: \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.

Fixpunkte

Elemente, deren Positionen sich bei der Permutation nicht ändern, nennt man Fixpunkte der Permutation. Bei der Permutation

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix}

sind dies beispielsweise die Zahlen 1 und 4. In der Matrixdarstellung erkennt man Fixpunkte daran, dass der obere und untere Eintrag der jeweiligen Spalte gleich ist. In der Zykelschreibweise sind Fixpunkte genau die Elemente, die nicht erscheinen. Für das obige Beispiel lautet die Zykelschreibweise (23); die Fixpunkte 1 und 4 erscheinen hier nicht. In der Permutationsmatrix sind die den Fixpunkten zugewiesenen Einträge der Hauptdiagonale 1. In der Permutationsmatrix zum obigen Beispiel sind dies die Einträge p1,1 und p4,4:

\begin{pmatrix}
    1 & 0 & 0 & 0\\
    0 & 0 & 1 & 0\\
    0 & 1 & 0 & 0\\
    0 & 0 & 0 & 1
\end{pmatrix}.

Eine Permutation ohne Fixpunkte wird auch Derangement genannt. Ein Derangement ist also ein „totale Versetzung“, bei der kein einziges Element auf seinem Platz bleibt. Die Anzahl der Derangements einer Menge mit n Elementen ist

n! \cdot\sum_{i=0}^n {\left(-1\right)^i \over i!}.

Diese Zahl heißt Subfakultät und wird mit !n bezeichnet.

Allgemeiner lässt sich die Anzahl der Permutationen mit einer gegebenen Anzahl von Fixpunkten (sog. partielle Derangements) mit Hilfe der Rencontres-Zahlen bestimmen.

Verknüpfung von Permutationen

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.

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: 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 Sn ist für n > 2 nicht abelsch. 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)

Ordnung

Für jede Permutation σ gibt es eine kleinste natürliche Zahl k derart, dass die k-malige Hintereinanderausführung von σ die Identität ergibt: σk = id. Diese Zahl wird Ordnung von σ genannt. Sie ist die Elementordnung von σ als Gruppenelement der Symmetrischen Gruppe. Die Ordnung einer Permutation lässt sich leicht aus der Zykeldarstellung bestimmen: Sie ist das kleinste gemeinsame Vielfache (kgV) der Längen der disjunkten Zykeln von σ. Beispielsweise ist die Ordnung der Permutation (124)(35) das kgV von 3 und 2, also 6.

Eine Permutation σ mit σ2 = id, oder äquivalent σ − 1 = σ, heißt Involution oder selbstinvers. Die Involutionen sind genau die Permutationen der Ordnung 2 sowie die Identität selbst (die einzige Permutation der Ordnung 1). Eine Permutation ist genau dann eine Involution, wenn ihre Zykeldarstellung maximal Zykel der Länge 2 (also Transpositionen) enthält.

Einige Eigenschaften von endlichen Permutationen

  • „left-to-right maximum“ (Links-Rechts-Maximum, kurz: LR-Maximum). Bei einer Permutation in Wortschreibweise a = a_1 \cdots a_i \cdots a_n nennt man ai ein LR-Maximum, genau dann wenn ai > aj mit 1 \leq j \leq i-1. Diese Eigenschaft ist von Nutzen, wenn man die normalisierte Zykeldarstellung ohne Klammern schreiben möchte. Man kann unter Ausnutzung der LR-Maxima zeigen, dass dann eine Bijektion zwischen der normalisierten Zykeldarstellung in eine Permutation existiert.[1] Bemerkung: a1 ist immer ein LR-Maximum.
  • Inversion/Fehlstand: Man nennt ein Paar (i,j) von Elementen Inversion bzgl. σ, falls gilt
    i < j und  \sigma\left(i\right) > \sigma\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(\sigma\right) die Anzahl der Inversionen von σ bezeichnet. Dann ist das Signum von σ gegeben durch \mathrm{sgn}\left(\sigma\right) = \left(-1\right)^{i\left(\sigma\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}(\sigma) = (-1)^{m_1+m_2+\cdots+m_r+r}

wobei r die Anzahl der Zykel und mi die Länge des i-ten Zykels sind \left(i=1,\ldots,r\right).

  • Typ: Sei mit bi die Anzahl der Zykel 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} \cdots 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.

Siehe auch

Literatur

Weblinks

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

Einzelnachweise

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • permutation — [ pɛrmytasjɔ̃ ] n. f. • 1474; « échange, troc » 1261; permutacion « changement de résidence » v. 1180; lat. permutatio 1 ♦ Échange d un emploi, d un poste contre un autre. Permutation de deux officiers, de deux fonctionnaires (⇒ permutant) . Par… …   Encyclopédie Universelle

  • Permutation — Permutation, die Bildung aller Anordnungen, in die eine Anzahl n von Elementen gebracht werden kann. Beispiel: a, b, c liefert sechs Permutationen: a b c, a c b, b a c, b c a, c a b, c b a. Eine Permutation heißt wohlgeordnet, wenn sie die… …   Lexikon der gesamten Technik

  • Permutation — Per mu*ta tion, n. [L. permutatio: cf. F. permutation. See {Permute}.] 1. The act of permuting; exchange of the thing for another; mutual transference; interchange. [1913 Webster] The violent convulsions and permutations that have been made in… …   The Collaborative International Dictionary of English

  • permutation — Permutation. subst. f. v. Eschange. Il ne se dit guere qu en parlant de l eschange d un Benefice contre un autre. Permutation de benefice …   Dictionnaire de l'Académie française

  • permutation — permutation. См. пермутация. (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

  • Permutation — (lat.), Vertauschung, Versetzung; in der Mathematik versteht man unter P. erstens jede Veränderung der Reihenfolge einer bestimmten Anzahl gegebener Dinge (Elemente), also die Tätigkeit (Operation), bei der jedes der gegebenen Elemente durch… …   Meyers Großes Konversations-Lexikon

  • Permutation — Permutatiōn (lat.), Vertauschung, Versetzung; in der Mathematik Veränderung der Reihenfolge einer bestimmten Anzahl gegebener Elemente. (S. Kombination.) …   Kleines Konversations-Lexikon

  • Permutation — Permutation, lat. deutsch, Vertauschung, Versetzung; in der Algebra die Umstellung gegebener Größen …   Herders Conversations-Lexikon

  • permutation — index exchange, mutuality Burton s Legal Thesaurus. William C. Burton. 2006 …   Law dictionary

  • permutation — mid 14c., from O.Fr. permutacion (14c.), from L. permutationem (nom. permutatio), from permutatus, pp. of permutare change thoroughly, exchange, from per thoroughly + mutare to change (see MUTABLE (Cf. mutable)) …   Etymology dictionary

  • permutation — mutation, *change, vicissitude, alternation Analogous words: moving or move, shifting or shift, removing or remove (see MOVE): transformation, conversion, metamorphosis (see under TRANSFORM) …   New Dictionary of Synonyms


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.