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]

Ist S_n die symmetrische Gruppe der Permutationen der Länge n und sind \pi = (\pi(1), \ldots , \pi(m)) \in S_m sowie \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

\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

\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 m verschoben an die erste angehängt und bei einer schiefen Summe die erste Permutation um n verschoben der zweiten vorangestellt.

Beispiele[Bearbeiten]

Die direkte Summe der beiden identischen Permutationen \pi = (1,2,3,4) \in S_4 und \sigma = (1,2,3) \in S_3 ergibt sich zu

\pi \oplus \sigma = (1,2,3,4,5,6,7) \in S_7,

während ihre schiefe Summe durch

\pi \ominus \sigma = (4,5,6,7,1,2,3) \in S_7

gegeben ist.

Matrixdarstellung[Bearbeiten]

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

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

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

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

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   P_{\pi \ominus \sigma} = \begin{pmatrix} 
0 & 0 & 0 & ~ 0 & 1 \\ 
0 & 0 & 0 & ~ 1 & 0 \\[2mm] 
0 & 0 & 1 & ~ 0 & 0 \\
1 & 0 & 0 & ~ 0 & 0 \\
0 & 1 & 0 & ~ 0 & 0 \\ 
\end{pmatrix}.

Eigenschaften[Bearbeiten]

Assoziativität[Bearbeiten]

Assoziativität direkter Summen von Permutationen

Die Bildung rein direkter und rein schiefer Summen ist assoziativ, das heißt für Permutationen \pi \in S_m, \sigma \in S_n und \tau \in S_k gilt

(\pi \oplus \sigma) \oplus \tau = \pi \oplus (\sigma \oplus \tau)

und

(\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

((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[Bearbeiten]

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

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

(\pi \oplus \sigma)^- = \pi^- \ominus \sigma^-

sowie

(\pi \ominus \sigma)^- = \pi^- \oplus \sigma^-.

Entsprechend ist die zu einer Permutation \pi \in S_n reverse Permutation \pi' = (\pi(n), \pi(n-1), \ldots , \pi(1)). Für die Reverse der Summe zweier Permutationen \pi \in S_m und \sigma \in S_n gilt

(\pi \oplus \sigma)' = \sigma' \ominus \pi'

sowie

(\pi \ominus \sigma)' = \sigma' \oplus \pi'.

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

Inverse[Bearbeiten]

Für die Inverse der Summe zweier Permutationen \pi \in S_m und \sigma \in S_n ergibt sich

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

sowie

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

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

Verwendung[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 n wird durch die (großen) Schröder-Zahlen 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[Bearbeiten]

Literatur[Bearbeiten]

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

Einzelnachweise[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. 65, 1998, S. 277–283.