Separable Permutation

Permutationsmatrizen aller 22 separablen Permutationen der Länge vier mit zugehöriger Blockstruktur

Eine separable Permutation ist in der Kombinatorik eine Permutation, die sich durch direkte oder schiefe Summen von trivialen Permutationen darstellen lässt. Die Permutationsmatrizen separabler Permutationen weisen damit eine rekursive Blockstruktur auf. Jeder separablen Permutation kann ein Separationsbaum, ein speziell bezeichneter geordneter Binärbaum, zugeordnet werden. Die Anzahl separabler Permutationen fester Länge wird durch die Schröder-Zahlen angegeben. Separable Permutationen werden unter anderem in der Sortierungstheorie untersucht.

Definition

Separable Permutationen werden wie folgt rekursiv definiert:

1. Die triviale Permutation der Länge eins ist separabel.
2. Sind die beiden Permutationen $\pi$ und $\sigma$ separabel, dann auch ihre direkte Summe $\pi \oplus \sigma$ und ihre schiefe Summe $\pi \ominus \sigma$.

Bei einer direkten Summe wird dabei die zweite Permutation verschoben an die erste angehängt, bei einer schiefen Summe die erste Permutation verschoben der zweiten vorangestellt. Separable Permutationen sind somit dadurch charakterisiert, dass sie sich durch direkte oder schiefe Summen trivialer Permutationen darstellen lassen.

Beispiele

Die beiden Permutationen der Länge zwei sind separabel, denn sie haben mit der trivialen Permutation $1=(1)$ die Darstellungen

$(1,2)=1\oplus 1$

$(2,1)=1\ominus 1$

Die sechs Permutationen der Länge drei sind ebenfalls alle separabel, denn sie haben folgende Darstellungen:

$(1,2,3)=(1\oplus 1)\oplus 1=1\oplus (1\oplus 1)$

$(1,3,2)=1\oplus (1\ominus 1)$

$(2,1,3)=(1\ominus 1)\oplus 1$

$(2,3,1)=(1\oplus 1)\ominus 1$

$(3,1,2)=1\ominus (1\oplus 1)$

$(3,2,1)=1\ominus (1\ominus 1)=(1\ominus 1)\ominus 1$

Von den 24 Permutationen der Länge vier sind zwei nicht separabel, nämlich die Permutationen $(2,4,1,3)$ und $(3,1,4,2)$.

Weitere Darstellungen

Permutationsmatrizen

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

Die Permutationsmatrizen separabler Permutationen zeichnen sich durch folgende rekursive Blockstruktur aus. Ist $\pi$ eine separable Permutation der Länge $n>1$ und $P\in \{0,1\}^{n\times n}$ die zugehörige Permutationsmatrix, dann gibt es einen Index $k\in \{1,\ldots ,n-1\}$, sodass entweder die beiden Untermatrizen

$P_{\{1,\ldots ,k\},\{k+1,\ldots ,n\}}$   und   $P_{\{k+1,\ldots ,n\},\{1,\ldots ,k\}}$

oder die beiden Untermatrizen

$P_{\{1,\ldots ,n-k\},\{1,\ldots ,k\}}$   und   $P_{\{n-k+1,\ldots ,n\},\{k+1,\ldots ,n\}}$

Nullmatrizen sind. Im ersten Fall hat die Permutation die Darstellung als direkte Summe

$\pi =(\pi (1),\ldots ,\pi (k))\oplus (\pi (k+1)-k,\ldots ,\pi (n)-k)$

und im zweiten Fall die Darstellung als schiefe Summe

$\pi =(\pi (1)-k,\ldots ,\pi (n-k)-k)\ominus (\pi (n-k+1),\ldots ,\pi (n))$.

Die beiden Summanden sind jeweils per Definition wiederum separable Permutationen und weisen daher ebenfalls eine entsprechende Blockstruktur auf. Die Blockzerlegung kann damit rekursiv bis zu den trivialen Permutationen fortgesetzt werden, die Blöcke der Größe $1\times 1$ bilden. Die Blockzerlegung einer gegebenen separablen Permutation muss allerdings nicht eindeutig sein, da die Bildung rein direkter und rein schiefer Summen assoziativ ist. Zum Beispiel kann bei einer identischen Permutation jede Zahl $k<n$ als trennender Index gewählt werden.

Separationsbäume

Zugehöriger Separationsbaum

Jeder separablen Permutation kann ein Separationsbaum (englisch separating tree), ein speziell bezeichneter geordneter Binärbaum, zugeordnet werden. Die Blätter des Separationsbaums werden von links nach rechts mit den Zahlen $\pi (1),\ldots ,\pi (n)$ bezeichnet. Den inneren Knoten wird ein $+$ oder ein $-$ zugeordnet, je nachdem, ob die beiden zugehörigen Teilbäume durch eine direkte oder eine schiefe Summe kombiniert werden. Im ersten Fall sind alle nachfolgenden Blätter des linken Teilbaums kleiner als diejenigen des rechten Teilbaums, im zweiten Fall umgekehrt. Jeder Teilbaum stellt wiederum eine separable Permutation mit entsprechend verschobenen Zahlen dar, wobei die Blätter für triviale Permutationen stehen. Die Blätter jedes Teilbaums bilden daher eine Menge aufeinander folgender Zahlen.

Nachdem die Summendarstellung einer separablen Permutation nicht eindeutig sein muss, können einer gegebenen separablen Permutation verschiedene Separationsbäume zugeordnet werden. Diese Bäume können jedoch durch Rotation benachbarter Knoten mit gleichem Vorzeichen ineinander umgewandelt werden. Demnach hat eine separable Permutation genau dann eine eindeutige Summendarstellung, wenn in dem zugeordneten Separationsbaum jeweils benachbarte Knoten unterschiedliche Vorzeichen aufweisen.

Aus dem Separationsbaum können auch die Fehlstände der Permutation abgelesen werden. Zwei Blätter bilden genau dann einen Fehlstand, wenn ihr kleinster gemeinsamer Vorgänger ein negatives Vorzeichen besitzt.

Klammerschreibweise

Separable Permutationen können auch folgendermaßen als Klammerausdruck geschrieben werden. Zunächst werden die Zahlen von $1$ bis $n$ in aufsteigender Reihenfolge nebeneinander notiert. Nun können um zwei oder mehr Zahlen Klammern gesetzt werden, sofern diese korrekt geschachtelt werden. Durch eine Klammer wird die Reihenfolge aller Zeichen innerhalb der Klammer umgekehrt. Nach Auswertung aller Klammern von außen nach innen ergibt sich dann die zugehörige separable Permutation in Tupelschreibweise. Beispielsweise gibt es für die Permutationen der Länge drei die folgenden möglichen Klammerungen:

Tupelschreibweise	(1,2,3)	(1,3,2)	(2,1,3)	(2,3,1)	(3,1,2)	(3,2,1)
Klammerschreibweise	1 2 3	1 [2 3]	[1 2] 3	[1 [2 3]]	[[1 2] 3]	[1 2 3]

Eine solche Klammerung kann in einen Separationsbaum umgewandelt werden, indem jeweils zwei nebeneinander stehende Zahlen oder Klammerblöcke einen inneren Knoten im Baum bilden. Ist die Schachtelungstiefe gerade, dann handelt es sich um einen positiven Knoten, ist sie ungerade, um einen negativen Knoten. Drei oder mehr nebeneinander stehende Zahlen oder Klammerblöcke können dabei in beliebiger Reihenfolge in Knoten gleichen Vorzeichens umgewandelt werden.

Eigenschaften

Anzahl

Separable Permutationen können durch Anfügen eines Wurzelknotens rekursiv aufgezählt werden, wenn der rechte Teilbaum ein anderes Vorzeichen als die Wurzel besitzt

Durch eine Aufzählung möglicher Separationsbäume kann die Anzahl separabler Permutationen gegebener Länge ermittelt werden. Eine eindeutige Zuordnung einer separablen Permutation zu einem Separationsbaum kann durch die Zusatzbedingung erreicht werden, dass der rechte Teilbaum eines inneren Knotens ein anderes Vorzeichen als der Knoten selbst aufweist. Jede separable Permutationen der Länge $n+1$ kann nun aus zwei separablen Permutationen kleinerer Länge durch Anfügen eines neuen Wurzelknotens generiert werden. Wird der Wurzelknoten mit $+$ bezeichnet, so kann als rechter Teilbaum entweder die triviale Permutation gewählt werden, wofür es $S_{1}=1$ Möglichkeiten gibt, oder eine separable Permutation der Länge $k=2,\ldots ,n$ mit negativer Wurzel, wofür es $S_{k}/2$ Möglichkeiten gibt. Als linker Teilbaum kann immer eine separable Permutation der Länge $n-k+1$ mit beliebiger Wurzel gewählt werden, wofür es $S_{n-k+1}$ Möglichkeiten gibt. Wird der Wurzelknoten mit $-$ bezeichnet, erhält man noch einmal die gleiche Anzahl von Möglichkeiten mit umgekehrten Vorzeichen. Insgesamt ergibt sich so für die Anzahl $S_{n}$ separabler Permutationen der Länge $n$ die Rekursion

$S_{n+1}=S_{n}+\sum _{k=1}^{n}S_{k}\cdot S_{n-k+1}$.

Die Zahlen $S_{n}$ werden (große) Schröder-Zahlen genannt und bilden die Folge

$1,2,6,22,90,394,1806,\ldots$   (Folge A006318 in OEIS).

Die erzeugende Funktion für die Anzahl der separablen Permutationen ist

$g(x)=\sum _{n=1}^{\infty }S_{n}x^{n}={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2}}$.

Symmetrien

Die zu einer Permutation $\pi$ der Länge $n$ komplementäre Permutation $\pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)$ und die entsprechend reverse Permutation $\pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))$ entstehen durch horizontale beziehungsweise vertikale Spiegelung der Permutationsmatrix. Ist eine Permutation separabel, so sind damit auch ihre komplementäre und ihre reverse Permutation separabel. Auch die Inverse $\pi ^{-1}$ einer separablen Permutation ist wieder separabel, da ihre Permutationsmatrix lediglich an der Hauptdiagonale gespiegelt ist.

Permutationsmuster

Eine Permutation ist genau dann separabel, wenn sie keine der beiden Permutationen $(2,4,1,3)$ und $(3,1,4,2)$ als Permutationsmuster, also als Teilpermutation mit dieser relativen Ordnung der Elemente, enthält. Jeder Permutation kann zudem ein Permutationsgraph zugeordnet werden, dessen Knoten die Elemente der Permutation und dessen Kanten den Fehlständen der Permutation entsprechen. Separable Permutationen sind genau diejenigen Permutationen, deren Permutationsgraphen Co-Graphen sind. Co-Graphen sind dadurch charakterisiert, dass sie keinen Pfad der Länge vier als induzierten Teilgraphen aufweisen, was gerade den beiden unzulässigen Permutationsmustern entspricht.

Ob eine gegebene separable Permutation ein Muster innerhalb einer längeren Permutation bildet lässt sich in Polynomialzeit überprüfen. Für nicht-separable Permutationen ist dieses Problem NP-vollständig.

Literatur

• 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, Chapter 2.2.5.