„Selbstinverse Permutation“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
Quartl (Diskussion | Beiträge) →Siehe auch: +1 |
Quartl (Diskussion | Beiträge) egf erg |
||
Zeile 143: | Zeile 143: | ||
die [[Doppelfakultät]] ist. Die Zahl <math>(2k-1)!!</math> entspricht gerade der Anzahl <math>I_{2k,k}</math> der echt involutorischen Permutationen in <math>S_{2k}</math>, also derjenigen Permutationen, die aus genau <math>k</math> disjunkten Transpositionen bestehen und somit den Zykeltyp <math>\operatorname{typ}(\pi) = 2^k</math> aufweisen ({{OEIS|A001147}}). |
die [[Doppelfakultät]] ist. Die Zahl <math>(2k-1)!!</math> entspricht gerade der Anzahl <math>I_{2k,k}</math> der echt involutorischen Permutationen in <math>S_{2k}</math>, also derjenigen Permutationen, die aus genau <math>k</math> disjunkten Transpositionen bestehen und somit den Zykeltyp <math>\operatorname{typ}(\pi) = 2^k</math> aufweisen ({{OEIS|A001147}}). |
||
== Erzeugende Funktionen == |
|||
Die exponentiell [[erzeugende Funktion]] der Folge <math>I_n</math> der Anzahl der selbstinversen Permutationen ergibt sich als<ref name="camina">{{Literatur|Autor=Alan Camina, Barry Lewis|Titel=An Introduction to Enumeration|Verlag=Springer|Jahr=2011|Seiten=141–142}}</ref> |
|||
:<math>f(x) = \sum_{n=0}^\infty I_n \frac{x^n}{n!} = e^{x+x^2/2}</math>. |
|||
Entsprechend ist die exponentiell erzeugende Funktion für die Anzahl der echt involutorischen Permutationen <math>I_{2k,k}</math> gleich<ref name="camina" /> |
|||
:<math>f(x) = \sum_{k=0}^\infty I_{2k,k} \frac{x^{2k}}{(2k)!} = e^{x^2/2}</math>. |
|||
== Anwendungen == |
== Anwendungen == |
||
Zeile 158: | Zeile 168: | ||
== Literatur == |
== Literatur == |
||
* {{Literatur|Autor=Alan Camina, Barry Lewis|Titel=An Introduction to Enumeration|Verlag=Springer|Jahr=2011|ISBN=0-857-29600-0}} |
|||
* {{Literatur|Autor=[[Philippe Flajolet]], [[Robert Sedgewick]]|Titel=Analytic Combinatorics|Verlag=Cambridge University Press|Jahr=2009|ISBN=1-139-47716-1}} |
* {{Literatur|Autor=[[Philippe Flajolet]], [[Robert Sedgewick]]|Titel=Analytic Combinatorics|Verlag=Cambridge University Press|Jahr=2009|ISBN=1-139-47716-1}} |
||
* {{Literatur|Autor=[[Donald Ervin Knuth|Donald E. Knuth]]|Titel=The Art of Computer Programming, Volume 3: Sorting and Searching|Auflage=2.|Verlag=Addison-Wesley|Jahr=1998|ISBN=0-201-89685-0}} |
* {{Literatur|Autor=[[Donald Ervin Knuth|Donald E. Knuth]]|Titel=The Art of Computer Programming, Volume 3: Sorting and Searching|Auflage=2.|Verlag=Addison-Wesley|Jahr=1998|ISBN=0-201-89685-0}} |
Version vom 19. Juli 2014, 11:16 Uhr
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 Zykeldarstellung 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.
Definition
Ist die symmetrische Gruppe aller Permutationen der Menge , dann heißt eine Permutation selbstinvers oder involutorisch, wenn sie gleich ihrer inversen Permutation ist, das heißt
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 involutorischen Permutation.
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.
Beispiele
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 Definition
- .
Weiter ist jede Vertauschung 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 involutorisch sind davon nur die Permutation und die drei Permutationen in , die je zwei Zahlenpaare vertauschen.
Eigenschaften
Nachdem ein Zyklus der Länge erst nach -maliger Hintereinanderausführung zur Identität zurückführen kann und die Zykeldarstellung 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 Zykeldarstellung ausschließlich aus Zyklen der Länge eins oder zwei besteht. Eine selbstinverse Permutation hat also die Zykeldarstellung
- ,
wobei die Anzahl der Zweier- und die Anzahl der Einerzykeln bezeichnet. Der Zykeltyp 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.
Anzahl
Rekursive Darstellung
|
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 auf Möglichkeiten geschehen kann.
- Ist ansonsten , dann muss gelten und die übrigen Zahlen müssen eine selbstinverse Permutation der Menge bilden, was auf Weisen geschehen kann.
Nachdem es Möglichkeiten für die Wahl von gibt, folgt daraus für die Anzahl der selbstinversen Permutationen die lineare Rekurrenz
- ,
wobei und sind. Die Anzahl der selbstinversen Permutationen ergibt für wachsendes die Folge
und ist gleich der Anzahl möglicher Young-Tableaus der Ordnung .[2]
Summendarstellung
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 ist. Die Zahlen genügen dabei der linearen Rekurrenz
(Folge A100861 in OEIS). Nachdem eine Permutation , die aus genau disjunkten Transpositionen besteht, den Zykeltyp besitzt, erhält man so die Summendarstellung[1]
- ,
wobei
die Doppelfakultät ist. Die Zahl entspricht gerade der Anzahl der echt involutorischen Permutationen in , also derjenigen Permutationen, die aus genau disjunkten Transpositionen bestehen und somit den Zykeltyp aufweisen (Folge A001147 in OEIS).
Erzeugende Funktionen
Die exponentiell erzeugende Funktion der Folge der Anzahl der selbstinversen Permutationen ergibt sich als[3]
- .
Entsprechend ist die exponentiell erzeugende Funktion für die Anzahl der echt involutorischen Permutationen gleich[3]
- .
Anwendungen
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 involutorische Permutationen führte die deutsche Verschlüsselungsmaschine Enigma durch, die während des Zweiten Weltkriegs zum Einsatz kam.
Eine spezielle selbstinverse Permutation wird zur Bitumkehrung bei der effizienten Implementierung der schnellen Fourier-Transformation (FFT) verwendet.[4]
Siehe auch
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, Volume 3: Sorting and Searching. 2. Auflage. Addison-Wesley, 1998, ISBN 0-201-89685-0.
Einzelnachweise
- ↑ a b Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, S. 122.
- ↑ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. 2. Auflage. Addison-Wesley, 1998, S. 48.
- ↑ a b Alan Camina, Barry Lewis: An Introduction to Enumeration. Springer, 2011, S. 141–142.
- ↑ Roland W. Freund, Ronald W. Hoppe: Stoer/Bulirsch: Numerische Mathematik 1, Band 1. 10. Auflage. Springer, 2007, S. 84.
Weblinks
- Eric W. Weisstein: Permutation involution. In: MathWorld (englisch).