Summe von Permutationen

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Permutationsmatrizen der direkten Summe (links) und der schiefen Summe (rechts) zweier Permutationen

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 | Quelltext 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.[1] 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 | Quelltext bearbeiten]

Die direkte Summe der beiden identischen Permutationen und ergibt sich zu

,

während ihre schiefe Summe durch

gegeben ist.

Matrixdarstellung[Bearbeiten | Quelltext 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

  und   .

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Assoziativität[Bearbeiten | Quelltext bearbeiten]

Assoziativität direkter Summen von Permutationen

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 | Quelltext bearbeiten]

Horizontale and vertikale Spiegelungen der Summe der Permutationen (3,2,1) und (1,2,3)

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 | Quelltext 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 | Quelltext bearbeiten]

Blockstrukturierung der Permutationsmatrix der separablen Permutation (4,3,5,1,2,7,8,6)

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.[2]

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.[3]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

  1. S. Kitaev: Patterns in Permutations and Words. Springer, 2011, S. 57.
  2. D. Avis, M. Newborn: On pop-stacks in series. In: Utilitas Mathematica. Nr. 19, 1981, S. 129–140.
  3. P. Bose, J. F. Buss, A. Lubiw: Pattern matching for permutations. In: Information Processing Letters. Band 65, 1998, S. 277–283.