imported>Hgzh: /* Rekursive Darstellung */ direkte Nutzung von thumb-Klassen vermeiden

2022-12-01T10:29:51Z

Rekursive Darstellung: direkte Nutzung von thumb-Klassen vermeiden

Neue Seite

[[Datei:050712 perm 4.png|mini|Graph einer selbstinversen Permutation der Zahlen von 1 bis 8. Die Permutation besteht nur aus Zyklen der Länge 1 oder 2.]]
Eine '''selbstinverse''' oder '''involutorische Permutation''' ist in der [[Kombinatorik]] und der [[Gruppentheorie]] eine [[Permutation]], die gleich ihrer [[Inverse Permutation|Inversen]] ist. Eine Permutation ist genau dann selbstinvers, wenn ihre [[Permutation#Zyklenschreibweise|Zyklendarstellung]] ausschließlich aus [[Zyklische Permutation|Zyklen]] der Länge eins oder zwei besteht. Die [[Ordnung eines Gruppenelements|Ordnung]] einer selbstinversen Permutation ist damit maximal zwei. Weiterhin ist die [[Permutationsmatrix]] einer selbstinversen Permutation immer [[Symmetrische Matrix|symmetrisch]]. Selbstinverse Permutationen spielen eine wichtige Rolle in der [[Kryptographie]].

== Definition ==
Ist <math>S_n</math> die [[symmetrische Gruppe]] aller [[Permutation]]en der Menge <math>\{ 1, \ldots , n \}</math>, dann heißt eine Permutation <math>\pi \in S_n</math> selbstinvers oder involutorisch, wenn sie gleich ihrer [[Inverse Permutation|inversen Permutation]] <math>\pi^{-1}</math> ist, wenn also

: <math>\pi = \pi^{-1}</math>

gilt. Eine dazu äquivalente Forderung ist<ref name="flajolet">{{Literatur |Autor=Philippe Flajolet, Robert Sedgewick |Titel=Analytic Combinatorics |Verlag=Cambridge University Press |Datum=2009 |Seiten=122}}</ref>

: <math>\pi^2 = \operatorname{id}</math>,

wobei <math>\pi^2 = \pi \circ \pi</math> die [[Komposition (Mathematik)|Hintereinanderausführung]] von <math>\pi</math> mit sich selbst und <math>\operatorname{id}</math> die [[identische Permutation]] sind. Eine selbstinverse Permutation stellt damit eine [[Involution (Mathematik)|Involution]] auf der Menge <math>\{ 1, \dotsc, n \}</math> dar. Hat eine selbstinverse Permutation zudem keine [[Fixpunkt (Mathematik)|Fixpunkte]], gilt also <math>\pi(i) \neq i</math> für alle <math>i=1, \dotsc, n</math>, so spricht man von einer ''echt selbstinversen Permutation''. Man nennt sie auch eine ''echt involutorische Permutation''.<ref>Friedrich L. Bauer: ''Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie.'' 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 49.</ref>

Allgemeiner können auch Permutationen beliebiger [[Endliche Menge|endlicher Mengen]], beispielsweise [[Alphabet (Informatik)|Alphabete]], betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten <math>n</math> natürlichen Zahlen beschränken.

== Beispiele ==
{| class="wikitable float-right" style="text-align:center"
|- class="hintergrundfarbe8"
!style="width:1.8em"| <math>n</math>
!colspan="3"| Selbstinverse Permutationen
! Anzahl
|-
|class="hintergrundfarbe8" | 1 || align="left" | id || || || 1
|-
|class="hintergrundfarbe8" | 2 || align="left" | id || align="left" | (1 2) || || 2
|-
|class="hintergrundfarbe8" | 3 || align="left" | id || align="left" | (1 2), (1 3), (2 3) || || 4
|-
|class="hintergrundfarbe8" | 4 || align="left" | id || align="left" | (1 2), (1 3), (1 4),<br />(2 3), (2 4), (3 4) || align="left" | (1 2) (3 4),<br />(1 3) (2 4),<br />(1 4) (2 3) || 10
|}

Die [[identische Permutation]] <math>\operatorname{id}</math> ist trivialerweise selbstinvers, denn es gilt per definitionem

: <math>\operatorname{id}^2 = \operatorname{id} \circ \operatorname{id} = \operatorname{id}</math>.

Weiter ist jede [[Vertauschung]] (Transposition) <math>\tau_{ij} = ( i ~ j )</math> zweier Zahlen <math>i</math> und <math>j</math> selbstinvers, denn die zweimalige Anwendung einer solchen Vertauschung tauscht die beiden Zahlen wieder zurück und es gilt damit

: <math>(\tau_{ij})^2 = ( i ~ j )( i ~ j ) = \operatorname{id}</math>.

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

: <math>\left( \tau_{i_1i_2} \circ \ldots \circ \tau_{i_{2k-1}i_{2k}} \right)^2 = (\tau_{i_1i_2})^2 \circ \ldots \circ (\tau_{i_{2k-1}i_{2k}})^2 = \operatorname{id} \circ \ldots \circ \operatorname{id} = \operatorname{id}</math>.

Die nebenstehende Tabelle führt alle selbstinversen Permutationen der symmetrischen Gruppen bis zum Grad vier auf. Echt selbstinvers sind davon nur die Permutation <math>(1~2) \in S_2</math> und die drei Permutationen in <math>S_4</math>, die je zwei Zahlenpaare vertauschen.

Ein weiteres Beispiel für eine selbstinverse Permutation ist die Spiegelung von n-Tupeln
: <math>\sigma_n = \begin{pmatrix} 1 & 2 & \dotsb & n \\ n & n-1 & \dotsb & 1 \end{pmatrix} = (1 ~ n)(2 ~ (n-1))(3 ~ (n-2))\cdots</math>,
siehe auch [[Wort (Theoretische Informatik)#Spiegelung|Wort (Theoretische Informatik) §Spiegelung]] und [[Palindrom#Definition|Palindrom]].

== Eigenschaften ==
Nachdem ein [[Zyklische Permutation|Zyklus]] der Länge <math>k</math> erst nach <math>k</math>-maliger Hintereinanderausführung zur Identität zurückführen kann und die [[Permutation#Zyklenschreibweise|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 <math>\pi \in S_n</math> hat also die Zyklendarstellung

: <math>\pi = (i_1 ~ i_2) \ldots (i_{2k-1} ~ i_{2k}) (i_{2k+1}) \ldots (i_n)</math>,

wobei <math>k \leq n/2</math> die Anzahl der Zweier- und <math>n-2k</math> die Anzahl der Einerzyklen bezeichnet. Der [[Zykeltyp|Zyklentyp]] einer selbstinversen Permutation <math>\pi</math> ist demnach von der Form

: <math>\operatorname{typ}(\pi) = 1^{n-2k}2^k</math>.

Die selbstinversen Permutationen sind damit genau die Permutationen der [[Ordnung eines Gruppenelements|Ordnung]] eins oder zwei, wobei die identische Permutation die einzige Permutation erster Ordnung ist. Die [[Permutationsmatrix]] <math>P_\pi</math> einer selbstinversen Permutation <math>\pi</math> ist immer [[Symmetrische Matrix|symmetrisch]], denn es gilt mit der [[Orthogonale Matrix|Orthogonalität]] von Permutationsmatrizen

: <math>P_\pi^T = P_\pi^{-1} = P_{\pi^{-1}} = P_\pi</math>.

Umgekehrt entspricht jede symmetrische Permutationsmatrix einer selbstinversen Permutation.

== Anzahl ==
=== Rekursive Darstellung ===
{{Manueller Rahmen
| content =
<div style="padding:10px; border-bottom:1px solid lightgray;"><math>\begin{pmatrix} 1 & 2 & 3 & \dotsb & n \\ 1 & \ast & \ast & \dotsb & \ast \end{pmatrix}</math></div>
<div style="padding:10px;"><math>\begin{pmatrix} 1 & 2 & 3 & \dotsb & n \\ 2 & 1 & \ast & \dotsb & \ast \end{pmatrix}</math></div>
| width = 220
| caption = Bei der Herleitung der Rekurrenz sind zwei Fälle zu unterscheiden: Entweder ist <math>\pi(1) = 1</math> oder es sind <math>\pi(1) = j \neq 1</math> und <math>\pi(j) = 1</math>. Im Beispiel ist <math>j=2</math>.
}}

Um die Anzahl <math>I_n</math> der selbstinversen Permutationen in der symmetrischen Gruppe <math>S_n</math> zu bestimmen, werden die folgenden zwei Fälle unterschieden:
* Gilt <math>\pi(1) = 1</math>, dann müssen die übrigen <math>n-1</math> Zahlen eine selbstinverse Permutation der Menge <math>\{ 2, \dotsc, n \}</math> bilden, was es <math>I_{n-1}</math> Möglichkeiten gibt.
* Ist ansonsten <math>\pi(1) = j \neq 1</math>, dann muss <math>\pi(j) = 1</math> gelten und die übrigen <math>n-2</math> Zahlen müssen eine selbstinverse Permutation der Menge <math>\{ 2, \dotsc, n \} \setminus \{ j \}</math> bilden, was auf <math>I_{n-2}</math> Arten geschehen kann.

Nachdem es <math>n-1</math> Möglichkeiten für die Wahl von <math>j</math> gibt, folgt daraus für die Anzahl der selbstinversen Permutationen die [[Lineare Differenzengleichung|lineare Rekurrenz]]

: <math>I_n = I_{n-1} + (n-1) I_{n-2}</math>

mit den Anfangswerten <math>I_1=1</math> und <math>I_2=2</math>. Die Anzahl der selbstinversen Permutationen ergibt für wachsendes <math>n</math> die Folge

: <math>1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, \dotsc</math> ({{OEIS|A000085}})

und ist gleich der Anzahl möglicher [[Young-Tableau]]s der Ordnung <math>n</math>.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art of Computer Programming, Volume 3: Sorting and Searching |Auflage=2. |Verlag=Addison-Wesley |Datum=1998 |Seiten=48}}</ref>

=== Summendarstellung ===
{| class="wikitable float-right" style="text-align:right"
|+ Anzahl der Permutationen von <math>n</math> Zahlen, die aus <math>k</math> disjunkten Transpositionen bestehen
|- class="hintergrundfarbe8"
|style="width:2em" | <math>{}_{n} \! \diagdown \!\! {}^{k}</math>
|style="width:2em" | 0
|style="width:2em" | 1
|style="width:2em" | 2
|style="width:2em" | 3
|style="width:2em" | 4
|style="width:2em" | 5
|style="width:2em" | Summe
|-
|class="hintergrundfarbe8" | 1 || 1 || || || || || || 1
|-
|class="hintergrundfarbe8" | 2 || 1 || 1 || || || || || 2
|-
|class="hintergrundfarbe8" | 3 || 1 || 3 || || || || || 4
|-
|class="hintergrundfarbe8" | 4 || 1 || 6 || 3 || || || || 10
|-
|class="hintergrundfarbe8" | 5 || 1 || 10 || 15 || || || || 26
|-
|class="hintergrundfarbe8" | 6 || 1 || 15 || 45 || 15 || || || 76
|-
|class="hintergrundfarbe8" | 7 || 1 || 21 || 105 || 105 || || || 232
|-
|class="hintergrundfarbe8" | 8 || 1 || 28 || 210 || 420 || 105 || || 764
|-
|class="hintergrundfarbe8" | 9 || 1 || 36 || 378 || 1260 || 945 || || 2620
|-
|class="hintergrundfarbe8" | 10 || 1 || 45 || 630 || 3150 || 4725 || 945 || 9496
|}

Bezeichnet <math>I_{n,k}</math> die Anzahl der Permutationen in <math>S_n</math>, die aus genau <math>k</math> disjunkten Transpositionen bestehen, dann gilt für die Anzahl der selbstinversen Permutationen

: <math>I_n = \sum_{k=0}^{\lfloor n/2 \rfloor} I_{n,k}</math>,

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

: <math>I_{n,k} = I_{n-1,k} + (n-2k+1) I_{n-1,k-1}</math> ({{OEIS|A100861}}).

Nachdem eine Permutation <math>\pi \in S_n</math>, die aus genau <math>k</math> disjunkten Transpositionen besteht, den Zyklentyp <math>\operatorname{typ}(\pi) = 1^{n-2k}2^k</math> besitzt, erhält man so die Summendarstellung<ref name="flajolet" />

: <math>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)!!</math>,

wobei

: <math>(2k-1)!! = 1 \cdot 3 \cdot \ldots \cdot (2k-1) = \frac{(2k)!}{k! \, 2^k}</math>

die [[Doppelfakultät]] ist. Die Zahl <math>(2k-1)!!</math> entspricht gerade der Anzahl <math>I_{2k,k}</math> der echt selbstinversen Permutationen in <math>S_{2k}</math>, also derjenigen Permutationen, die aus genau <math>k</math> disjunkten Transpositionen bestehen und somit den Zyklentyp <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 |Datum=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 der Folge <math>I_{2k,k}</math> der Anzahl der echt selbstinversen Permutationen gleich<ref name="camina" />

: <math>f(x) = \sum_{k=0}^\infty I_{2k,k} \frac{x^{2k}}{(2k)!} = e^{x^2/2}</math>.

== Anwendungen ==
[[Datei:Enigma-action-de.svg|mini|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 <math>13</math> Stellen im Alphabet verschobenen Buchstaben ersetzt wird. Die wiederholte Anwendung ergibt dann eine Verschiebung um <math>26</math> Buchstaben und damit wieder die ursprüngliche Nachricht. Eine weitere Möglichkeit einer solchen Verschlüsselung besteht in der Verwendung der bitweisen [[Kontravalenz|XOR-Operation]], die beispielsweise beim [[One-Time-Pad]] verwendet wird. Sehr viel komplexere echt selbstinverse Permutationen führte die deutsche Verschlüsselungsmaschine [[Enigma (Maschine)|Enigma]] durch, die während des Zweiten Weltkriegs zum Einsatz kam.

Die echt selbstinversen Permutationen werden auch zur Berechnung der [[Pfaffsche Determinante|pfaffschen Determinante]] einer [[Alternierende Matrix|alternierenden Matrix]] benötigt. Eine spezielle selbstinverse Permutation wird zur Bitumkehrung bei der effizienten Implementierung der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT) verwendet.<ref>{{Literatur |Autor=Roland W. Freund, Ronald W. Hoppe |Titel=Numerische Mathematik |TitelErg=1 |Band=1 |Hrsg=Stoer, Bulirsch |Auflage=10. |Verlag=Springer |Datum=2007 |Seiten=84}}</ref>

== Literatur ==
* {{Literatur
|Autor=Alan Camina, Barry Lewis
|Titel=An Introduction to Enumeration
|Verlag=Springer
|Datum=2011
|ISBN=0-85729-600-0}}
* {{Literatur
|Autor=[[Philippe Flajolet]], [[Robert Sedgewick (Informatiker)|Robert Sedgewick]]
|Titel=Analytic Combinatorics
|Verlag=Cambridge University Press
|Datum=2009
|ISBN=1-139-47716-1}}
* {{Literatur
|Autor=[[Donald E. Knuth]]
|Titel=The Art of Computer Programming
|Band=Volume 3: Sorting and Searching
|Auflage=2.
|Verlag=Addison-Wesley
|Datum=1998
|ISBN=0-201-89685-0}}

== Weblinks ==
* {{MathWorld |id=PermutationInvolution |title=Permutation involution}}

== Einzelnachweise ==
<references />

[[Kategorie:Permutationstheorie]]

Selbstinverse Permutation - Versionsgeschichte

imported>Hgzh: /* Rekursive Darstellung */ direkte Nutzung von thumb-Klassen vermeiden