Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:59 Fr 26.05.2006 | | Autor: | Sunny85 |
| Aufgabe | | Man finde eine rekursive Formel für die Anzahl u(n) der Permutationen von [n], deren vierte Potenz die identische Permutation ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß nicht, wie ich an die Aufgabe herangehen soll, um dann eine Formel zu entwickeln. Ist mit der vierten Potenz gemeint, das es z.B. eine Permutation p gibt für die gilt: [mm] p^4 [/mm] = id ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:27 Fr 26.05.2006 | | Autor: | felixf |
Hoi Sunny!
> Man finde eine rekursive Formel für die Anzahl u(n) der
> Permutationen von [n], deren vierte Potenz die identische
> Permutation ist.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Ich weiß nicht, wie ich an die Aufgabe herangehen soll, um
> dann eine Formel zu entwickeln. Ist mit der vierten Potenz
> gemeint, das es z.B. eine Permutation p gibt für die gilt:
> [mm]p^4[/mm] = id ?
Es ist gemeint, dass du alle Permutation $p$ mit [mm] $p^4 [/mm] = id$ finden sollst. Solche Permutationen sind genau die, bei denen die Zerlegung in disjunkte Zyklen nur Zyklen der Laenge 1, 2 und 4 haben.
Nimm an, du willst $[n]$ bestimmen. Sei $p$ eine Permutation von [mm] $\{ 1, \dots, n \}$ [/mm] mit [mm] $p^4 [/mm] = id$. Dann hast du drei Faelle:
1) $p(n) = n$. Von dieser Sorte gibt es genau $[n-1]$ Stueck.
2) $p(n) [mm] \neq [/mm] n$, aber [mm] $p^2(n) [/mm] = p(p(n)) = n$. Von dieser Sorte gibt es genau $(n - 1) [mm] \cdot [/mm] [n-2]$ Stueck (weisst du warum?).
2) $p(n) [mm] \neq [/mm] n$ und [mm] $p^2(n) [/mm] = p(p(n)) [mm] \neq [/mm] n$, aber [mm] $p^4(n) [/mm] = p(p(p(p(n)))) = n$. Von dieser Sorte gibt es genau $(n - 1) [mm] \cdot [/mm] (n - 2) [mm] \cdot [/mm] (n - 3) [mm] \cdot [/mm] [n-4]$ Stueck (weisst du warum?).
LG Felix
|
|
|
|
