Summe von Permutationen

Grundidee und Definition

Eine Summe von Permutationen ist eine Verknüpfung aus der Kombinatorik: Aus zwei Permutationen entsteht eine neue Permutation, deren Länge die Summe der beiden ursprünglichen Längen ist. Es gibt die direkte Summe ⊕ und die schiefe Summe ⊖.

Für π=(π(1),…,π(m))∈S_m und σ=(σ(1),…,σ(n))∈S_n gilt:

π⊕σ=(π(1),…,π(m), σ(1)+m,…,σ(n)+m)∈S_{m+n}.

Dabei wird σ um m verschoben und hinter π gesetzt. Dagegen ist

π⊖σ=(π(1)+n,…,π(m)+n, σ(1),…,σ(n))∈S_{m+n}.

Hier wird π um n verschoben und vor σ gesetzt. S_n bezeichnet die symmetrische Gruppe, also die Menge aller Permutationen der Länge n.

Beispiel

Für π=(1,2,3,4)∈S_4 und σ=(1,2,3)∈S_3 ergibt die direkte Summe

π⊕σ=(1,2,3,4,5,6,7)∈S_7.

Die Einträge von σ werden dafür um 4 erhöht. Die schiefe Summe lautet dagegen

π⊖σ=(4,5,6,7,1,2,3)∈S_7,

weil die Einträge von π um 3 erhöht werden.

Darstellung durch Matrizen

Zu einer Permutation π∈S_n gehört eine Permutationsmatrix P_π, also eine n×n-Matrix mit Einträgen aus {0,1}. Die Summen zeigen sich darin als Blockmatrizen:

P_{π⊕σ}=((P_π,0),(0,P_σ))

und

P_{π⊖σ}=((0,P_π),(P_σ,0)).

Dabei steht 0 jeweils für eine Nullmatrix passender Größe. Bei der direkten Summe liegen die Matrizen von π und σ auf der Hauptdiagonale. Bei der schiefen Summe stehen sie in den beiden anderen Blöcken. Diese Blockstruktur entspricht genau dem Verschieben und Aneinanderfügen der Permutationen.

Rechenregeln, Symmetrien und Inverse

Rein direkte und rein schiefe Summen sind assoziativ. Für π∈S_m, σ∈S_n und τ∈S_k gilt daher

(π⊕σ)⊕τ=π⊕(σ⊕τ)

sowie

(π⊖σ)⊖τ=π⊖(σ⊖τ).

Bei einer Mischung beider Operationen gilt dies im Allgemeinen nicht: ((1)⊕(1))⊖(1)=(2,3,1) ist verschieden von (1)⊕((1)⊖(1))=(1,3,2). Auch das Kommutativgesetz ist im Allgemeinen nicht erfüllt.

Das Komplement von π∈S_n ist π⁻=(n−π(1)+1,…,n−π(n)+1). Dafür gelten die Regeln (π⊕σ)⁻=π⁻⊖σ⁻ und (π⊖σ)⁻=π⁻⊕σ⁻. Die reverse Permutation ist π′=(π(n),π(n−1),…,π(1)); hier gilt (π⊕σ)′=σ′⊖π′ sowie (π⊖σ)′=σ′⊕π′. In den Permutationsmatrizen entsprechen diese beiden Operationen Spiegelungen an einer horizontalen beziehungsweise vertikalen Achse.

Für die Inverse gilt (π⊕σ)⁻¹=π⁻¹⊕σ⁻¹ und (π⊖σ)⁻¹=σ⁻¹⊖π⁻¹. Die zugehörigen Permutationsmatrizen werden dabei an der Hauptdiagonale gespiegelt, also transponiert.

Bedeutung und separable Permutationen

Direkte und schiefe Summen dienen dazu, Permutationen in Grundbausteine zu zerlegen. Wegen der Assoziativität ist eine solche Zerlegung nicht notwendigerweise eindeutig.

Permutationen, die sich vollständig als direkte oder schiefe Summe trivialer Permutationen darstellen lassen, heißen separable Permutationen. Ihre Anzahl für die Länge n wird durch die großen Schröder-Zahlen S_n angegeben; dies ist die Folge A006318 in OEIS. Separable Permutationen besitzen eine besondere rekursive Blockstruktur ihrer Permutationsmatrizen und werden unter anderem in der Sortierungstheorie untersucht.

Die beiden Summen sind außerdem beim Studium von Permutationsmustern wichtig. Die Zerlegung in nicht weiter zerlegbare Teilpermutationen ermöglicht es, bestimmte Klassen solcher Muster zu charakterisieren und zu zählen.