Separable Permutation

Grundidee und rekursive Definition

Eine separable Permutation ist eine Permutation, die sich aus der trivialen Permutation der Länge eins durch direkte Summen und schiefe Summen aufbauen lässt. Sie ist in der Kombinatorik und unter anderem in der Sortierungstheorie von Bedeutung.

Rekursiv gilt:

• Die triviale Permutation der Länge eins ist separabel.
• Sind (pi und (sigma separabel, dann sind auch ihre direkte Summe (pi (oplus (sigma und ihre schiefe Summe (pi (ominus (sigma separabel.

Bei der direkten Summe wird die zweite Permutation verschoben an die erste angehängt. Bei der schiefen Summe wird die erste Permutation verschoben der zweiten vorangestellt. Damit sind genau die Permutationen separabel, die durch solche Summen trivialer Permutationen darstellbar sind.

Kleine Beispiele

Für die triviale Permutation (1=(1) gilt:

• ((1,2)=1(oplus 1
• ((2,1)=1(ominus 1

Alle sechs Permutationen der Länge drei sind separabel. Beispiele für ihre Darstellungen sind ((1,3,2)=1(oplus(1(ominus1), ((2,1,3)=(1(ominus1)(oplus1 und ((2,3,1)=(1(oplus1)(ominus1.

Von den 24 Permutationen der Länge vier sind genau zwei nicht separabel: ((2,4,1,3) und ((3,1,4,2).

Darstellungen durch Matrizen, Bäume und Klammern

Die Permutationsmatrix einer separablen Permutation der Länge (n>1 besitzt eine rekursive Blockstruktur. Es gibt einen trennenden Index (k(in{1,ldots,n-1}), bei dem passende außerdiagonale Untermatrizen Nullmatrizen sind. Im einen Fall entspricht dies einer direkten, im anderen einer schiefen Summe. Diese Zerlegung wird bis zu Blöcken der Größe (1(times1 fortgesetzt. Sie ist nicht immer eindeutig: Da rein direkte und rein schiefe Summen assoziativ sind, kann bei einer identischen Permutation jedes (k<n als trennender Index dienen.

Ein Separationsbaum ist ein speziell bezeichneter geordneter Binärbaum. Seine Blätter tragen von links nach rechts die Zahlen (pi(1),ldots,pi(n). Innere Knoten erhalten ein (+ für direkte und ein (- für schiefe Summen. Bei einem positiven Knoten sind alle nachfolgenden Blätter des linken Teilbaums kleiner als die des rechten Teilbaums; bei einem negativen Knoten ist es umgekehrt. Die Blätter jedes Teilbaums bilden eine Menge aufeinander folgender Zahlen. Verschiedene Bäume derselben Permutation lassen sich durch Rotation benachbarter Knoten mit gleichem Vorzeichen ineinander überführen. Eine Summendarstellung ist genau dann eindeutig, wenn benachbarte Knoten unterschiedliche Vorzeichen haben. Zwei Blätter bilden genau dann einen Fehlstand, wenn ihr kleinster gemeinsamer Vorgänger negativ ist.

Auch eine Klammerschreibweise ist möglich: Man schreibt zunächst (1,ldots,n aufsteigend und setzt korrekt geschachtelte Klammern um mindestens zwei Zahlen. Jede Klammer kehrt die Reihenfolge aller enthaltenen Zeichen um; die Auswertung erfolgt von außen nach innen. So liefert (1[23] die Permutation ((1,3,2), während ([1[23]] die Permutation ((2,3,1) liefert. Aus einer Klammerung entsteht ein Separationsbaum; gerade Schachtelungstiefe bedeutet einen positiven, ungerade Tiefe einen negativen Knoten.

Anzahl, Symmetrien und Muster

Die Anzahl (S_n separabler Permutationen der Länge (n sind die großen Schröder-Zahlen. Mit einer eindeutigen Baumdarstellung, bei der der rechte Teilbaum eines inneren Knotens ein anderes Vorzeichen als der Knoten besitzt, ergibt sich die Rekursion

(S_{n+1}=S_n+sum_{k=1}^{n}S_kcdot S_{n-k+1}.

Die Folge lautet

(1,2,6,22,90,394,1806,ldots

und ist als Folge A006318 in OEIS verzeichnet. Ihre erzeugende Funktion ist

(g(x)=sum_{n=1}^{infty}S_nx^n=frac{1-x-sqrt{1-6x+x^2}}{2}.

Separabilität bleibt bei drei Symmetrien erhalten: bei der komplementären Permutation (pi^-=(n-pi(1)+1,ldots,n-pi(n)+1), bei der reversen Permutation (pi'=(pi(n),pi(n-1),ldots,pi(1)) sowie bei der Inversen (pi^{-1}. Diese entsprechen horizontaler, vertikaler beziehungsweise diagonal an der Hauptdiagonale erfolgender Spiegelung der Permutationsmatrix.

Eine Permutation ist genau dann separabel, wenn sie weder ((2,4,1,3) noch ((3,1,4,2) als Permutationsmuster enthält. Ein Permutationsmuster ist eine Teilpermutation mit derselben relativen Ordnung. Der Permutationsgraph hat die Elemente der Permutation als Knoten und die Fehlstände als Kanten. Separable Permutationen sind genau die Permutationen, deren Permutationsgraph Co-Graph ist. Co-Graphen enthalten keinen Pfad der Länge vier als induzierten Teilgraphen; dies entspricht genau den beiden verbotenen Mustern. Ob eine separable Permutation ein Muster in einer längeren Permutation bildet, ist in Polynomialzeit entscheidbar; für nicht-separable Permutationen ist dieses Problem NP-vollständig.