fixpunktfreie Involutionen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:38 Mi 30.07.2008 | | Autor: | myro |
| Aufgabe | | Eine monoalphabetische Verschlüsselung des Alphabets entspricht einer Permutation der 26 Buchstaben. Wieviele Möglichkeiten gibt es, wenn man nur Permutationen betrachtet, die keinen Buchstaben auf sich selbst abbilden und ihr eigenes Inverses sind? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ok. Es gibt 26! Permutationen. Ich wollte das ganze jetzt in 2 Schritte zerlegen: Erstmal nich auf sich selbst abbilden, dann das Inverse noch wegglasen.
Schritt 1: Da ich zB. a nicht auf a abbilden kann bleiben hab ich schon zu Beginn nur 25 Möglichkeiten für den ersten Buchstaben -> 25! (Bin mir selbst hier sehr unsicher, bei einem Alphabet mit 3 Buchstaben, hat es zumindest gestimmt...)
Schritt 2: ???? ich hab jetzt schon länger darüber nachgedacht und mir fällt hierzu einfach nicht ein, wie ich auf die zahl der Inversen Elemente kommen lönnte.
Die Lösung ist im Buch übrigens angegeben:
25*23*...*3*1
Wodurch ich denke, dass auch mein erster Schritt falsch ist. Für Idenn wäre ich dankbar.
|
|
| |
|
> Eine monoalphabetische Verschlüsselung des Alphabets
> entspricht einer Permutation der 26 Buchstaben. Wieviele
> Möglichkeiten gibt es, wenn man nur Permutationen
> betrachtet, die keinen Buchstaben auf sich selbst abbilden
> und ihr eigenes Inverses sind?
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Ok. Es gibt 26! Permutationen. Ich wollte das ganze jetzt
> in 2 Schritte zerlegen: Erstmal nich auf sich selbst
> abbilden, dann das Inverse noch wegglasen.
> Schritt 1: Da ich zB. a nicht auf a abbilden kann bleiben
> hab ich schon zu Beginn nur 25 Möglichkeiten für den ersten
> Buchstaben -> 25! (Bin mir selbst hier sehr unsicher, bei
> einem Alphabet mit 3 Buchstaben, hat es zumindest
> gestimmt...)
>
> Schritt 2: ???? ich hab jetzt schon länger darüber
> nachgedacht und mir fällt hierzu einfach nicht ein, wie ich
> auf die zahl der Inversen Elemente kommen lönnte.
>
> Die Lösung ist im Buch übrigens angegeben:
> 25*23*...*3*1
>
> Wodurch ich denke, dass auch mein erster Schritt falsch
> ist. Für Idenn wäre ich dankbar.
Wenn ich die Aufgabe richtig verstehe sollen also die Permutationen von $n=26$ Elementen gezählt werden, die ihre eigenen Inversen sind und keine Fixpunkte besitzen. Dies sind gerade die Permutationen, deren Zyklenzerlegung ausschliesslich aus Zyklen der Länge 2 besteht (also keine Zyklen der Länge 1 besitzen, somit keine Fixpunkte, und auch keine Zyklen grösserer Länge als 2, weil sie sonst nicht ihre eigenen Inversen wären).
|
|
|
| |
|
Man kann solche fixpunktfreien involutiven Permutationen
schrittweise konstruieren:
Der Buchstabe a kann auf irgendeinen der anderen 25 abge-
bildet werden: 25 Möglichkeiten. Wird a beispielsweise auf k
abgebildet, bleiben für die Wahl eines "Partners" für b noch
alle Buchstaben ausser a,k und b, also insgesamt 23 Möglich-
keiten, und so weiter...
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:23 Mi 30.07.2008 | | Autor: | myro |
Vielen Dank! So macht das Sinn.
|
|
|
|
