Selbstinverse Permutation

Eine selbstinverse oder involutorische Permutation ist in der Kombinatorik und der Gruppentheorie eine Permutation, die gleich ihrer Inversen ist. Eine Permutation ist genau dann selbstinvers, wenn ihre Zyklendarstellung ausschließlich aus Zyklen der Länge eins oder zwei besteht. Die Ordnung einer selbstinversen Permutation ist damit maximal zwei. Weiterhin ist die Permutationsmatrix einer selbstinversen Permutation immer symmetrisch. Selbstinverse Permutationen spielen eine wichtige Rolle in der Kryptographie.

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

DefinitionBearbeiten

Ist   die symmetrische Gruppe aller Permutationen der Menge  , dann heißt eine Permutation   selbstinvers oder involutorisch, wenn sie gleich ihrer inversen Permutation   ist, wenn also

 

gilt. Eine dazu äquivalente Forderung ist[1]

 ,

wobei   die Hintereinanderausführung von   mit sich selbst und   die identische Permutation sind. Eine selbstinverse Permutation stellt damit eine Involution auf der Menge   dar. Hat eine selbstinverse Permutation zudem keine Fixpunkte, gilt also   für alle  , 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   natürlichen Zahlen beschränken.

BeispieleBearbeiten

  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   ist trivialerweise selbstinvers, denn es gilt per definitionem

 .

Weiter ist jede Vertauschung (Transposition)   zweier Zahlen   und   selbstinvers, denn die zweimalige Anwendung einer solchen Vertauschung tauscht die beiden Zahlen wieder zurück und es gilt damit

 .

Auch die mehrfache Vertauschung   paarweise verschiedener Zahlen   stellt eine selbstinverse Permutation dar, denn aufgrund der Disjunktheit der Zyklen gilt entsprechend

 .

Die nebenstehende Tabelle führt alle selbstinversen Permutationen der symmetrischen Gruppen bis zum Grad vier auf. Echt selbstinvers sind davon nur die Permutation   und die drei Permutationen in  , die je zwei Zahlenpaare vertauschen.

Ein weiteres Beispiel für eine selbstinverse Permutation ist die Spiegelung von n-Tupeln

 ,

siehe auch Wort (Theoretische Informatik) §Spiegelung und Palindrom.

EigenschaftenBearbeiten

Nachdem ein Zyklus der Länge   erst nach  -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   hat also die Zyklendarstellung

 ,

wobei   die Anzahl der Zweier- und   die Anzahl der Einerzyklen bezeichnet. Der Zyklentyp einer selbstinversen Permutation   ist demnach von der Form

 .

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   einer selbstinversen Permutation   ist immer symmetrisch, denn es gilt mit der Orthogonalität von Permutationsmatrizen

 .

Umgekehrt entspricht jede symmetrische Permutationsmatrix einer selbstinversen Permutation.

AnzahlBearbeiten

Rekursive DarstellungBearbeiten

 
 
Bei der Herleitung der Rekurrenz sind zwei Fälle zu unterscheiden: Entweder ist   oder es sind   und  . Im Beispiel ist  .

Um die Anzahl   der selbstinversen Permutationen in der symmetrischen Gruppe   zu bestimmen, werden die folgenden zwei Fälle unterschieden:

  • Gilt  , dann müssen die übrigen   Zahlen eine selbstinverse Permutation der Menge   bilden, was es   Möglichkeiten gibt.
  • Ist ansonsten  , dann muss   gelten und die übrigen   Zahlen müssen eine selbstinverse Permutation der Menge   bilden, was auf   Arten geschehen kann.

Nachdem es   Möglichkeiten für die Wahl von   gibt, folgt daraus für die Anzahl der selbstinversen Permutationen die lineare Rekurrenz

 

mit den Anfangswerten   und  . Die Anzahl der selbstinversen Permutationen ergibt für wachsendes   die Folge

  (Folge A000085 in OEIS)

und ist gleich der Anzahl möglicher Young-Tableaus der Ordnung  .[3]

SummendarstellungBearbeiten

Anzahl der Permutationen von   Zahlen, die aus   disjunkten Transpositionen bestehen
  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   die Anzahl der Permutationen in  , die aus genau   disjunkten Transpositionen bestehen, dann gilt für die Anzahl der selbstinversen Permutationen

 ,

wobei   die Gaußklammer darstellt und   für alle   gilt. Die Zahlen   genügen dabei der linearen Rekurrenz

  (Folge A100861 in OEIS).

Nachdem eine Permutation  , die aus genau   disjunkten Transpositionen besteht, den Zyklentyp   besitzt, erhält man so die Summendarstellung[1]

 ,

wobei

 

die Doppelfakultät ist. Die Zahl   entspricht gerade der Anzahl   der echt selbstinversen Permutationen in  , also derjenigen Permutationen, die aus genau   disjunkten Transpositionen bestehen und somit den Zyklentyp   aufweisen (Folge A001147 in OEIS).

Erzeugende FunktionenBearbeiten

Die exponentiell erzeugende Funktion der Folge   der Anzahl der selbstinversen Permutationen ergibt sich als[4]

 .

Entsprechend ist die exponentiell erzeugende Funktion der Folge   der Anzahl der echt selbstinversen Permutationen gleich[4]

 .

AnwendungenBearbeiten

 
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   Stellen im Alphabet verschobenen Buchstaben ersetzt wird. Die wiederholte Anwendung ergibt dann eine Verschiebung um   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 echt selbstinversen Permutationen werden auch zur Berechnung der pfaffschen Determinante einer alternierenden Matrix benötigt. Eine spezielle selbstinverse Permutation wird zur Bitumkehrung bei der effizienten Implementierung der schnellen Fourier-Transformation (FFT) verwendet.[5]

LiteraturBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. a b 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. a b 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.