Selbstinverse Permutation

Eine selbstinverse o​der involutorische Permutation i​st in d​er Kombinatorik u​nd der Gruppentheorie e​ine Permutation, d​ie gleich i​hrer Inversen ist. Eine Permutation i​st genau d​ann selbstinvers, w​enn ihre Zyklendarstellung ausschließlich a​us Zyklen d​er Länge e​ins oder z​wei besteht. Die Ordnung e​iner selbstinversen Permutation i​st damit maximal zwei. Weiterhin i​st die Permutationsmatrix e​iner selbstinversen Permutation i​mmer symmetrisch. Selbstinverse Permutationen spielen e​ine wichtige Rolle i​n der Kryptographie.

Graph einer selbstinversen Permutation der Zahlen von 1 bis 8. Die Permutation besteht nur aus Zyklen der Länge 1 oder 2.

Definition

Ist ${\displaystyle S_{n}}$ die symmetrische Gruppe aller Permutationen der Menge ${\displaystyle \{1,\ldots ,n\}}$, dann heißt eine Permutation ${\displaystyle \pi \in S_{n}}$ selbstinvers oder involutorisch, wenn sie gleich ihrer inversen Permutation ${\displaystyle \pi ^{-1}}$ ist, wenn also

${\displaystyle \pi =\pi ^{-1}}$

gilt. Eine d​azu äquivalente Forderung ist[1]

${\displaystyle \pi ^{2}=\operatorname {id} }$,

wobei ${\displaystyle \pi ^{2}=\pi \circ \pi }$ die Hintereinanderausführung von ${\displaystyle \pi }$ mit sich selbst und ${\displaystyle \operatorname {id} }$ die identische Permutation sind. Eine selbstinverse Permutation stellt damit eine Involution auf der Menge ${\displaystyle \{1,\dotsc ,n\}}$ dar. Hat eine selbstinverse Permutation zudem keine Fixpunkte, gilt also ${\displaystyle \pi (i)\neq i}$ für alle ${\displaystyle i=1,\dotsc ,n}$, so spricht man von einer echt selbstinversen Permutation. Man nennt sie auch eine echt involutorische Permutation.[2]

Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten ${\displaystyle n}$ natürlichen Zahlen beschränken.

Beispiele

${\displaystyle n}$	Selbstinverse Permutationen			Anzahl
1	id			1
2	id	(1 2)		2
3	id	(1 2), (1 3), (2 3)		4
4	id	(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)	(1 2) (3 4), (1 3) (2 4), (1 4) (2 3)	10

Die identische Permutation ${\displaystyle \operatorname {id} }$ ist trivialerweise selbstinvers, denn es gilt per definitionem

${\displaystyle \operatorname {id} ^{2}=\operatorname {id} \circ \operatorname {id} =\operatorname {id} }$.

Weiter ist jede Vertauschung (Transposition) ${\displaystyle \tau _{ij}=(i~j)}$ zweier Zahlen ${\displaystyle i}$ und ${\displaystyle j}$ selbstinvers, denn die zweimalige Anwendung einer solchen Vertauschung tauscht die beiden Zahlen wieder zurück und es gilt damit

${\displaystyle (\tau _{ij})^{2}=(i~j)(i~j)=\operatorname {id} }$.

Auch die mehrfache Vertauschung ${\displaystyle (i_{1}~i_{2})\ldots (i_{2k-1}~i_{2k})}$ paarweise verschiedener Zahlen ${\displaystyle i_{1},\dotsc ,i_{2k}}$ stellt eine selbstinverse Permutation dar, denn aufgrund der Disjunktheit der Zyklen gilt entsprechend

${\displaystyle \left(\tau _{i_{1}i_{2}}\circ \ldots \circ \tau _{i_{2k-1}i_{2k}}\right)^{2}=(\tau _{i_{1}i_{2}})^{2}\circ \ldots \circ (\tau _{i_{2k-1}i_{2k}})^{2}=\operatorname {id} \circ \ldots \circ \operatorname {id} =\operatorname {id} }$.

Die nebenstehende Tabelle führt alle selbstinversen Permutationen der symmetrischen Gruppen bis zum Grad vier auf. Echt selbstinvers sind davon nur die Permutation ${\displaystyle (1~2)\in S_{2}}$ und die drei Permutationen in ${\displaystyle S_{4}}$, die je zwei Zahlenpaare vertauschen.

Ein weiteres Beispiel für e​ine selbstinverse Permutation i​st die Spiegelung v​on n-Tupeln

${\displaystyle \sigma _{n}={\begin{pmatrix}1&2&\dotsb &n\\n&n-1&\dotsb &1\end{pmatrix}}=(1~n)(2~(n-1))(3~(n-2))\cdots }$,

siehe a​uch Wort (Theoretische Informatik) §Spiegelung u​nd Palindrom.

Eigenschaften

Nachdem ein Zyklus der Länge ${\displaystyle k}$ erst nach ${\displaystyle k}$-maliger Hintereinanderausführung zur Identität zurückführen kann und die Zyklendarstellung einer Permutation (bis auf die Reihenfolge der Zyklen und die Anordnung der Zahlen innerhalb der Zyklen) eindeutig ist, ist eine Permutation genau dann selbstinvers, wenn ihre Zyklendarstellung ausschließlich aus Zyklen der Länge eins oder zwei besteht. Eine selbstinverse Permutation ${\displaystyle \pi \in S_{n}}$ hat also die Zyklendarstellung

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

wobei ${\displaystyle k\leq n/2}$ die Anzahl der Zweier- und ${\displaystyle n-2k}$ die Anzahl der Einerzyklen bezeichnet. Der Zyklentyp einer selbstinversen Permutation ${\displaystyle \pi }$ ist demnach von der Form

${\displaystyle \operatorname {typ} (\pi )=1^{n-2k}2^{k}}$.

Die selbstinversen Permutationen sind damit genau die Permutationen der Ordnung eins oder zwei, wobei die identische Permutation die einzige Permutation erster Ordnung ist. Die Permutationsmatrix ${\displaystyle P_{\pi }}$ einer selbstinversen Permutation ${\displaystyle \pi }$ ist immer symmetrisch, denn es gilt mit der Orthogonalität von Permutationsmatrizen

${\displaystyle P_{\pi }^{T}=P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }}$.

Umgekehrt entspricht j​ede symmetrische Permutationsmatrix e​iner selbstinversen Permutation.

Anzahl

Rekursive Darstellung

${\displaystyle {\begin{pmatrix}1&2&3&\dotsb &n\\1&\ast &\ast &\dotsb &\ast \end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}1&2&3&\dotsb &n\\2&1&\ast &\dotsb &\ast \end{pmatrix}}}$ Bei der Herleitung der Rekurrenz sind zwei Fälle zu unterscheiden: Entweder ist ${\displaystyle \pi (1)=1}$ oder es sind ${\displaystyle \pi (1)=j\neq 1}$ und ${\displaystyle \pi (j)=1}$. Im Beispiel ist ${\displaystyle j=2}$.

Um die Anzahl ${\displaystyle I_{n}}$ der selbstinversen Permutationen in der symmetrischen Gruppe ${\displaystyle S_{n}}$ zu bestimmen, werden die folgenden zwei Fälle unterschieden:

• Gilt ${\displaystyle \pi (1)=1}$, dann müssen die übrigen ${\displaystyle n-1}$ Zahlen eine selbstinverse Permutation der Menge ${\displaystyle \{2,\dotsc ,n\}}$ bilden, was es ${\displaystyle I_{n-1}}$ Möglichkeiten gibt.
• Ist ansonsten ${\displaystyle \pi (1)=j\neq 1}$, dann muss ${\displaystyle \pi (j)=1}$ gelten und die übrigen ${\displaystyle n-2}$ Zahlen müssen eine selbstinverse Permutation der Menge ${\displaystyle \{2,\dotsc ,n\}\setminus \{j\}}$ bilden, was auf ${\displaystyle I_{n-2}}$ Arten geschehen kann.

Nachdem es ${\displaystyle n-1}$ Möglichkeiten für die Wahl von ${\displaystyle j}$ gibt, folgt daraus für die Anzahl der selbstinversen Permutationen die lineare Rekurrenz

${\displaystyle I_{n}=I_{n-1}+(n-1)I_{n-2}}$

mit den Anfangswerten ${\displaystyle I_{1}=1}$ und ${\displaystyle I_{2}=2}$. Die Anzahl der selbstinversen Permutationen ergibt für wachsendes ${\displaystyle n}$ die Folge

${\displaystyle 1,2,4,10,26,76,232,764,2620,9496,\dotsc }$ (Folge A000085 in OEIS)

und ist gleich der Anzahl möglicher Young-Tableaus der Ordnung ${\displaystyle n}$.[3]

Summendarstellung

Anzahl der Permutationen von ${\displaystyle n}$ Zahlen, die aus ${\displaystyle k}$ disjunkten Transpositionen bestehen

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	0	1	2	3	4	5	Summe
1	1						1
2	1	1					2
3	1	3					4
4	1	6	3				10
5	1	10	15				26
6	1	15	45	15			76
7	1	21	105	105			232
8	1	28	210	420	105		764
9	1	36	378	1260	945		2620
10	1	45	630	3150	4725	945	9496

Bezeichnet ${\displaystyle I_{n,k}}$ die Anzahl der Permutationen in ${\displaystyle S_{n}}$, die aus genau ${\displaystyle k}$ disjunkten Transpositionen bestehen, dann gilt für die Anzahl der selbstinversen Permutationen

${\displaystyle I_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }I_{n,k}}$,

wobei ${\displaystyle \lfloor ~\rfloor }$ die Gaußklammer darstellt und ${\displaystyle I_{n,0}=1}$ für alle ${\displaystyle n}$ gilt. Die Zahlen ${\displaystyle I_{n,k}}$ genügen dabei der linearen Rekurrenz

${\displaystyle I_{n,k}=I_{n-1,k}+(n-2k+1)I_{n-1,k-1}}$ (Folge A100861 in OEIS).

Nachdem eine Permutation ${\displaystyle \pi \in S_{n}}$, die aus genau ${\displaystyle k}$ disjunkten Transpositionen besteht, den Zyklentyp ${\displaystyle \operatorname {typ} (\pi )=1^{n-2k}2^{k}}$ besitzt, erhält man so die Summendarstellung[1]

${\displaystyle I_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{(n-2k)!\,k!\,2^{k}}}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}(2k-1)!!}$,

wobei

${\displaystyle (2k-1)!!=1\cdot 3\cdot \ldots \cdot (2k-1)={\frac {(2k)!}{k!\,2^{k}}}}$

die Doppelfakultät ist. Die Zahl ${\displaystyle (2k-1)!!}$ entspricht gerade der Anzahl ${\displaystyle I_{2k,k}}$ der echt selbstinversen Permutationen in ${\displaystyle S_{2k}}$, also derjenigen Permutationen, die aus genau ${\displaystyle k}$ disjunkten Transpositionen bestehen und somit den Zyklentyp ${\displaystyle \operatorname {typ} (\pi )=2^{k}}$ aufweisen (Folge A001147 in OEIS).

Erzeugende Funktionen

Die exponentiell erzeugende Funktion der Folge ${\displaystyle I_{n}}$ der Anzahl der selbstinversen Permutationen ergibt sich als[4]

${\displaystyle f(x)=\sum _{n=0}^{\infty }I_{n}{\frac {x^{n}}{n!}}=e^{x+x^{2}/2}}$.

Entsprechend ist die exponentiell erzeugende Funktion der Folge ${\displaystyle I_{2k,k}}$ der Anzahl der echt selbstinversen Permutationen gleich[4]

${\displaystyle f(x)=\sum _{k=0}^{\infty }I_{2k,k}{\frac {x^{2k}}{(2k)!}}=e^{x^{2}/2}}$.

Anwendungen

Vertauschung von Buchstaben durch die Verschlüsselungsmaschine Enigma

In der Kryptographie spielen selbstinverse Permutationen eine wichtige Rolle. Wird eine Nachricht mit Hilfe einer selbstinversen Permutation verschlüsselt, dann lässt sich die Nachricht mittels der gleichen Permutation auch wieder entschlüsseln. Ein einfaches Beispiel ist die Caesar-Verschlüsselung ROT13, bei der zur Verschlüsselung jeder Buchstabe durch den um ${\displaystyle 13}$ Stellen im Alphabet verschobenen Buchstaben ersetzt wird. Die wiederholte Anwendung ergibt dann eine Verschiebung um ${\displaystyle 26}$ Buchstaben und damit wieder die ursprüngliche Nachricht. Eine weitere Möglichkeit einer solchen Verschlüsselung besteht in der Verwendung der bitweisen XOR-Operation, die beispielsweise beim One-Time-Pad verwendet wird. Sehr viel komplexere echt selbstinverse Permutationen führte die deutsche Verschlüsselungsmaschine Enigma durch, die während des Zweiten Weltkriegs zum Einsatz kam.

Die e​cht selbstinversen Permutationen werden a​uch zur Berechnung d​er pfaffschen Determinante e​iner alternierenden Matrix benötigt. Eine spezielle selbstinverse Permutation w​ird zur Bitumkehrung b​ei der effizienten Implementierung d​er schnellen Fourier-Transformation (FFT) verwendet.[5]

Literatur

• Alan Camina, Barry Lewis: An Introduction to Enumeration. Springer, 2011, ISBN 0-85729-600-0.
• Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, ISBN 1-139-47716-1.
• Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0.

Weblinks

• Eric W. Weisstein: Permutation involution. In: MathWorld (englisch).

Einzelnachweise

1. Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, S. 122.
2. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 49.
3. Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. 2. Auflage. Addison-Wesley, 1998, S. 48.
4. Alan Camina, Barry Lewis: An Introduction to Enumeration. Springer, 2011, S. 141–142.
5. Roland W. Freund, Ronald W. Hoppe: Numerische Mathematik. 1. Hrsg.: Stoer, Bulirsch. 10. Auflage. Band 1. Springer, 2007, S. 84.