Eine Summe von Permutationen ist in der Kombinatorik eine Verknüpfung zweier Permutationen, durch die eine neue Permutation entsteht. Die Länge der Ergebnispermutation entspricht dabei der Summe der Längen der beiden Ausgangspermutationen. Man unterscheidet zwei Möglichkeiten der Summenbildung, die direkte Summe und die schiefe Summe. Bei der direkten Summe wird die zweite Permutation verschoben an die erste angehängt, bei der schiefen Summe die erste Permutation verschoben der zweiten vorangestellt. Die zugehörigen Permutationsmatrizen weisen eine entsprechende Blockstruktur auf.
Die Bildung rein direkter oder rein schiefer Summen von Permutationen ist assoziativ, für gemischte direkte und schiefe Summen gilt jedoch das Assoziativgesetz im Allgemeinen nicht. Summen komplementärer oder reverser Permutationen lassen sich durch Summen der Ausgangspermutationen darstellen. Auch die Inverse einer Summe von Permutationen ergibt sich als Summe von Inversen. Direkte und schiefe Summen von Permutationen spielen eine wichtige Rolle bei der Zerlegung von Permutationen in ihre Grundbausteine und bei der Charakterisierung separabler Permutationen.
Definition Bearbeiten
Ist die symmetrische Gruppe der Permutationen der Länge und sind sowie zwei Permutationen in Tupelschreibweise nicht notwendigerweise gleicher Länge, dann wird ihre direkte Summe (englisch direct sum) durch
und ihre schiefe Summe (englisch skew sum) durch
definiert. In Tupelschreibweise wird demnach bei einer direkten Summe die zweite Permutation um verschoben an die erste angehängt und bei einer schiefen Summe die erste Permutation um verschoben der zweiten vorangestellt.
Beispiele Bearbeiten
Die direkte Summe der beiden identischen Permutationen und ergibt sich zu
während ihre schiefe Summe durch
gegeben ist.
Matrixdarstellung Bearbeiten
Ist die zur Permutation zugehörige Permutationsmatrix, dann ist die Permutationsmatrix der direkten Summe zweier Permutationen und eine Blockmatrix der Form
und die Permutationsmatrix der entsprechenden schiefen Summe eine Blockmatrix der Form
Hierbei steht jeweils für eine Nullmatrix passender Größe. Sind beispielsweise und , dann ergibt sich
Eigenschaften Bearbeiten
Assoziativität Bearbeiten
Die Bildung rein direkter und rein schiefer Summen ist assoziativ, das heißt für Permutationen , und gilt
und
Für gemischte direkte und schiefe Summen gilt jedoch das Assoziativgesetz im Allgemeinen nicht, wie das Beispiel
zeigt. Auch das Kommutativgesetz ist im Allgemeinen nicht erfüllt.
Symmetrien Bearbeiten
Die zu einer Permutation komplementäre Permutation ist . Für das Komplement der Summe zweier Permutationen und gilt
sowie
Entsprechend ist die zu einer Permutation reverse Permutation . Für die Reverse der Summe zweier Permutationen und gilt
sowie
Die zugehörigen Permutationsmatrizen sind entsprechend an einer horizontalen beziehungsweise vertikalen Achse gespiegelt.
Inverse Bearbeiten
Für die Inverse der Summe zweier Permutationen und ergibt sich
sowie
Die zugehörigen Permutationsmatrizen sind jeweils an der Hauptdiagonale gespiegelt, also transponiert.
Verwendung Bearbeiten
Direkte und schiefe Summen spielen in der Kombinatorik eine wichtige Rolle bei der Zerlegung von Permutationen in ihre Grundbausteine. Eine solche Zerlegung ist allerdings aufgrund der Assoziativität der Summenbildung nicht notwendigerweise eindeutig. Diejenigen Permutationen, die sich vollständig als direkte oder schiefe Summe trivialer Permutationen darstellen lassen, heißen separable Permutationen. Die Anzahl separabler Permutationen der Länge wird durch die (großen) Schröder-Zahlen angegeben (Folge A006318 in OEIS). Separable Permutationen zeichnen sich durch eine spezielle rekursive Blockstrukturierung der zugehörigen Permutationsmatrizen aus. Sie werden unter anderem in der Sortierungstheorie untersucht.
Direkte und schiefe Summen treten auch beim Studium von Permutationsmustern (englisch permutation pattern) auf. Die Zerlegung von Permutationen in nicht weiter zerlegbare Teilpermutationen erlaubt die Charakterisierung und Aufzählung bestimmter Patternklassen.
Siehe auch Bearbeiten
- Direkte Summe von Vektorräumen
- Direktes Produkt von Gruppen und anderen algebraischen Strukturen
Literatur Bearbeiten
- Miklós Bóna: Combinatorics of Permutations (= Discrete Mathematics and Its Applications. Nr. 72). 2. Auflage. CRC Press, 2012, ISBN 1-4398-5051-8.
- Sergey Kitaev: Patterns in Permutations and Words (= Monographs in theoretical computer science). Springer, 2011, ISBN 978-3-642-17333-2.
Einzelnachweise Bearbeiten
- S. Kitaev: Patterns in Permutations and Words. Springer, 2011, S. 57.
- D. Avis, M. Newborn: On pop-stacks in series. In: Utilitas Mathematica. Nr. 19, 1981, S. 129–140.
- P. Bose, J. F. Buss, A. Lubiw: Pattern matching for permutations. In: Information Processing Letters. Band 65, 1998, S. 277–283.