Summe von Permutationen

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

Ist ${\displaystyle S_{n}}$ die symmetrische Gruppe der Permutationen der Länge ${\displaystyle n}$ und sind ${\displaystyle \pi =(\pi (1),\ldots ,\pi (m))\in S_{m}}$ sowie ${\displaystyle \sigma =(\sigma (1),\ldots ,\sigma (n))\in S_{n}}$ zwei Permutationen in Tupelschreibweise nicht notwendigerweise gleicher Länge, dann wird ihre direkte Summe (englisch direct sum) durch

${\displaystyle \pi \oplus \sigma =(\pi (1),\ldots ,\pi (m),~\sigma (1)+m,\ldots ,\sigma (n)+m)\in S_{m+n}}$

und ihre schiefe Summe (englisch skew sum) durch

${\displaystyle \pi \ominus \sigma =(\pi (1)+n,\ldots ,\pi (m)+n,~\sigma (1),\ldots ,\sigma (n))\in S_{m+n}}$.

definiert.^[1] In Tupelschreibweise wird demnach bei einer direkten Summe die zweite Permutation um ${\displaystyle m}$ verschoben an die erste angehängt und bei einer schiefen Summe die erste Permutation um ${\displaystyle n}$ verschoben der zweiten vorangestellt.

Beispiele

Die direkte Summe der beiden identischen Permutationen ${\displaystyle \pi =(1,2,3,4)\in S_{4}}$ und ${\displaystyle \sigma =(1,2,3)\in S_{3}}$ ergibt sich zu

${\displaystyle \pi \oplus \sigma =(1,2,3,4,5,6,7)\in S_{7}}$,

während ihre schiefe Summe durch

${\displaystyle \pi \ominus \sigma =(4,5,6,7,1,2,3)\in S_{7}}$

gegeben ist.

Matrixdarstellung

Ist ${\displaystyle P_{\pi }\in \{0,1\}^{n\times n}}$ die zur Permutation ${\displaystyle \pi \in S_{n}}$ zugehörige Permutationsmatrix, dann ist die Permutationsmatrix der direkten Summe zweier Permutationen ${\displaystyle \pi \in S_{m}}$ und ${\displaystyle \sigma \in S_{n}}$ eine Blockmatrix der Form

${\displaystyle P_{\pi \oplus \sigma }={\begin{pmatrix}P_{\pi }&0\\0&P_{\sigma }\end{pmatrix}}}$

und die Permutationsmatrix der entsprechenden schiefen Summe eine Blockmatrix der Form

${\displaystyle P_{\pi \ominus \sigma }={\begin{pmatrix}0&P_{\pi }\\P_{\sigma }&0\end{pmatrix}}}$.

Hierbei steht jeweils ${\displaystyle 0}$ für eine Nullmatrix passender Größe. Sind beispielsweise ${\displaystyle \pi =(3,1,2)\in S_{3}}$ und ${\displaystyle \sigma =(2,1)\in S_{2}}$, dann ergibt sich

${\displaystyle P_{\pi \oplus \sigma }={\begin{pmatrix}0&0&1&~0&0\\1&0&0&~0&0\\0&1&0&~0&0\\[2mm]0&0&0&~0&1\\0&0&0&~1&0\\\end{pmatrix}}}$   und   ${\displaystyle P_{\pi \ominus \sigma }={\begin{pmatrix}0&0&~0&0&1\\0&0&~1&0&0\\0&0&~0&1&0\\[2mm]0&1&~0&0&0\\1&0&~0&0&0\\\end{pmatrix}}}$.

Eigenschaften

Assoziativität

Assoziativität direkter Summen von Permutationen

Die Bildung rein direkter und rein schiefer Summen ist assoziativ, das heißt für Permutationen ${\displaystyle \pi \in S_{m}}$, ${\displaystyle \sigma \in S_{n}}$ und ${\displaystyle \tau \in S_{k}}$ gilt

${\displaystyle (\pi \oplus \sigma )\oplus \tau =\pi \oplus (\sigma \oplus \tau )}$

und

${\displaystyle (\pi \ominus \sigma )\ominus \tau =\pi \ominus (\sigma \ominus \tau )}$.

Für gemischte direkte und schiefe Summen gilt jedoch das Assoziativgesetz im Allgemeinen nicht, wie das Beispiel

${\displaystyle ((1)\oplus (1))\ominus (1))=(2,3,1)\neq (1,3,2)=(1)\oplus ((1)\ominus (1))}$

zeigt. Auch das Kommutativgesetz ist im Allgemeinen nicht erfüllt.

Symmetrien

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

Die zu einer Permutation ${\displaystyle \pi \in S_{n}}$ komplementäre Permutation ist ${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$. Für das Komplement der Summe zweier Permutationen ${\displaystyle \pi \in S_{m}}$ und ${\displaystyle \sigma \in S_{n}}$ gilt

${\displaystyle (\pi \oplus \sigma )^{-}=\pi ^{-}\ominus \sigma ^{-}}$

sowie

${\displaystyle (\pi \ominus \sigma )^{-}=\pi ^{-}\oplus \sigma ^{-}}$.

Entsprechend ist die zu einer Permutation ${\displaystyle \pi \in S_{n}}$ reverse Permutation ${\displaystyle \pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))}$. Für die Reverse der Summe zweier Permutationen ${\displaystyle \pi \in S_{m}}$ und ${\displaystyle \sigma \in S_{n}}$ gilt

${\displaystyle (\pi \oplus \sigma )'=\sigma '\ominus \pi '}$

sowie

${\displaystyle (\pi \ominus \sigma )'=\sigma '\oplus \pi '}$.

Die zugehörigen Permutationsmatrizen sind entsprechend an einer horizontalen beziehungsweise vertikalen Achse gespiegelt.

Inverse

Für die Inverse der Summe zweier Permutationen ${\displaystyle \pi \in S_{m}}$ und ${\displaystyle \sigma \in S_{n}}$ ergibt sich

${\displaystyle (\pi \oplus \sigma )^{-1}=\pi ^{-1}\oplus \sigma ^{-1}}$

sowie

${\displaystyle (\pi \ominus \sigma )^{-1}=\sigma ^{-1}\ominus \pi ^{-1}}$.

Die zugehörigen Permutationsmatrizen sind jeweils an der Hauptdiagonale gespiegelt, also transponiert.

Verwendung

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 ${\displaystyle n}$ wird durch die (großen) Schröder-Zahlen ${\displaystyle S_{n}}$ 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

• Direktes Produkt von Gruppen und anderen algebraischen Strukturen
• Direkte Summe von Vektorräumen

Literatur

• Sergey Kitaev: Patterns in Permutations and Words (= Monographs in theoretical computer science). Springer, 2011, ISBN 978-3-642-17333-2. 
• Miklós Bóna: Combinatorics of Permutations (= Discrete Mathematics and Its Applications. Nr. 72). 2. Auflage. CRC Press, 2012, ISBN 1-4398-5051-8. 

Einzelnachweise

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.