Permutationsmatrizen

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

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

oder die beiden Untermatrizen

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

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

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

und im zweiten Fall die Darstellung als schiefe Summe

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle k<n}$ als trennender Index gewählt werden.

Separationsbäume

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 ${\displaystyle \pi (1),\ldots ,\pi (n)}$ bezeichnet. Den inneren Knoten wird ein ${\displaystyle +}$ oder ein ${\displaystyle -}$ 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 ${\displaystyle 1}$ bis ${\displaystyle 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:

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.

Anzahl

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 ${\displaystyle n+1}$ kann nun aus zwei separablen Permutationen kleinerer Länge durch Anfügen eines neuen Wurzelknotens generiert werden. Wird der Wurzelknoten mit ${\displaystyle +}$ bezeichnet, so kann als rechter Teilbaum entweder die triviale Permutation gewählt werden, wofür es ${\displaystyle S_{1}=1}$ Möglichkeiten gibt, oder eine separable Permutation der Länge ${\displaystyle k=2,\ldots ,n}$ mit negativer Wurzel, wofür es ${\displaystyle S_{k}/2}$ Möglichkeiten gibt. Als linker Teilbaum kann immer eine separable Permutation der Länge ${\displaystyle n-k+1}$ mit beliebiger Wurzel gewählt werden, wofür es ${\displaystyle S_{n-k+1}}$ Möglichkeiten gibt. Wird der Wurzelknoten mit ${\displaystyle -}$ bezeichnet, erhält man noch einmal die gleiche Anzahl von Möglichkeiten mit umgekehrten Vorzeichen. Insgesamt ergibt sich so für die Anzahl ${\displaystyle S_{n}}$ separabler Permutationen der Länge ${\displaystyle n}$ die Rekursion

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

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

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

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

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

Symmetrien

Die zu einer Permutation ${\displaystyle \pi }$ der Länge ${\displaystyle n}$ komplementäre Permutation ${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$ und die entsprechend reverse Permutation ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle (2,4,1,3)}$ und ${\displaystyle (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.