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 Bearbeiten
Separable Permutationen werden wie folgt rekursiv definiert:
- Die triviale Permutation der Länge eins ist separabel.
- Sind die beiden Permutationen und separabel, dann auch ihre direkte Summe und ihre schiefe Summe .
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 Bearbeiten
Die beiden Permutationen der Länge zwei sind separabel, denn sie haben mit der trivialen Permutation die Darstellungen
Die sechs Permutationen der Länge drei sind ebenfalls alle separabel, denn sie haben folgende Darstellungen:
Von den 24 Permutationen der Länge vier sind zwei nicht separabel, nämlich die Permutationen und .
Weitere Darstellungen Bearbeiten
Permutationsmatrizen Bearbeiten
Die Permutationsmatrizen separabler Permutationen zeichnen sich durch folgende rekursive Blockstruktur aus. Ist eine separable Permutation der Länge und die zugehörige Permutationsmatrix, dann gibt es einen Index , sodass entweder die beiden Untermatrizen
oder die beiden Untermatrizen
Nullmatrizen sind. Im ersten Fall hat die Permutation die Darstellung als direkte Summe
und im zweiten Fall die Darstellung als schiefe Summe
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 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 als trennender Index gewählt werden.
Separationsbäume Bearbeiten
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 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 Bearbeiten
Separable Permutationen können auch folgendermaßen als Klammerausdruck geschrieben werden. Zunächst werden die Zahlen von bis 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 Bearbeiten
Anzahl Bearbeiten
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 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 Möglichkeiten gibt, oder eine separable Permutation der Länge mit negativer Wurzel, wofür es Möglichkeiten gibt. Als linker Teilbaum kann immer eine separable Permutation der Länge mit beliebiger Wurzel gewählt werden, wofür es 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 separabler Permutationen der Länge die Rekursion
Die Zahlen werden (große) Schröder-Zahlen genannt und bilden die Folge
Die erzeugende Funktion für die Anzahl der separablen Permutationen ist
Symmetrien Bearbeiten
Die zu einer Permutation der Länge komplementäre Permutation und die entsprechend reverse Permutation 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 einer separablen Permutation ist wieder separabel, da ihre Permutationsmatrix lediglich an der Hauptdiagonale gespiegelt ist.
Permutationsmuster Bearbeiten
Eine Permutation ist genau dann separabel, wenn sie keine der beiden Permutationen und 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 Bearbeiten
- 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.
Einzelnachweise Bearbeiten
- D. Avis, M. Newborn: On pop-stacks in series. In: Utilitas Mathematica. Nr. 19, 1981, S. 129–140.
- ↑ P. Bose, J. F. Buss, A. Lubiw: Pattern matching for permutations. In: Information Processing Letters. Band 65, 1998, S. 277–283.
- L. Shapiro, A. B. Stephens: Bootstrap percolation, the Schröder numbers, and the N-kings problem. In: SIAM Journal on Discrete Mathematics. Band 4, 1991, S. 275–280.
- M. H. Albert, M. D. Atkinson, V. Vatter: Subclasses of the separable permutations. In: Bulletin of the London Mathematical Society. Band 43, Nr. 5, 2011, S. 859–870.