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.[1]

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

Definition

Bearbeiten

Separable Permutationen werden wie folgt rekursiv definiert:

  1. Die triviale Permutation der Länge eins ist separabel.
  2. 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
 
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   eine separable Permutation der Länge   und   die zugehörige Permutationsmatrix, dann gibt es einen Index  , sodass entweder die beiden Untermatrizen

    und    

oder die beiden Untermatrizen

    und    

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
 
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   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.[2]

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
 
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.[3] 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

    (Folge A006318 in OEIS).

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

 .

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.[2]

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.[2]

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
  1. D. Avis, M. Newborn: On pop-stacks in series. In: Utilitas Mathematica. Nr. 19, 1981, S. 129–140.
  2. a b c P. Bose, J. F. Buss, A. Lubiw: Pattern matching for permutations. In: Information Processing Letters. Band 65, 1998, S. 277–283.
  3. 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.
  4. 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.