Direkt zum Inhalt

Lexikon der Mathematik: Permutation

bijektive Abbildung einer Menge auf sich.

Auf einer n-elementigen Menge gibt es n! Permutationen; diese bilden bezüglich Hintereinanderausführung eine Gruppe, die meist mit Sn bezeichnete symmetrische Gruppe oder Permutationsgruppe.

Für n ≥ 3 ist Sn nicht kommutativ. Ein Element π aus Sn wird oft in der Form \begin{eqnarray}\pi =\left(\begin{array}{cccc}1 & 2 & \cdots & n\\ \pi (1) & \pi (2) & \cdots & \pi (n)\end{array}\right)\end{eqnarray} angegeben.

Ein Fixpunkt der Permutation π ist ein i mit π(i) = i. π heißt zyklisch oder ein Zykel, wenn eine Teilmenge {x1,…,xr} ⊂ {1,…,n} existiert mit π(xi) = xi+1 für 1 ≤ i < r, π(xr) = x1 und π(xl) = xl sonst. In der sogenannten Zykelschreib-weise schreibt man ein solches π als (x1,…,xr), r wird als Länge der Permutation bezeichnet. Die einzige zyklische Permutation der Länge 1 ist die Identität; zyklische Permutationen der Länge 2 heißen Transpositionen.

Jede Permutation ist Produkt von Transpositionen; diese Darstellung ist nicht eindeutig, jedoch ist jede Permutation entweder stets das Produkt von geradzahlig vielen Permutationen oder von ungeradzahlig vielen Permutationen; entsprechend wird die Permutation als gerade oder ungerade bezeichnet. Jede Permutation läßt sich als Produkt elementfremder Zykel schreiben.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos