unzerlegbare Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:05 So 26.04.2015 | | Autor: | caesars |
Wir nennen eine Permutation [mm] \sigma [/mm] = [mm] a_1 \dots a_n \in S_n [/mm] unzerlegbar, falls
[mm] {a_1 , \dots a_j} \neq [/mm] [j] [mm] \forall [/mm] j<n. Sei f(n) die Anzahl der unzerlegbaren Permutationen in [mm] S_n. [/mm] Zeigen:
i) [mm] \sum_{j=1}^n [/mm] f(j)(n-j)! = n! für [mm] n\geq [/mm] 1
ii) [mm] (\sum_{n\geq=1}f(n)t^n)(\sum_{n\geq=0}n!t^n) [/mm] = [mm] (\sum_{n\geq=1}n!t^n) [/mm] - 1
zu i habe ich den Hinweis gefunden:
Es sei [mm] A_i [/mm] die Menge all jener Permutationen [mm] \sigma\in S_n, [/mm] für die [mm] \sigma([i])=[i] [/mm] und [mm] \sigma([j]) \neq [/mm] [j] für alle 1 [mm] \leq [/mm] j < i gilt.
Offenkundig ist [mm] A_1\cup A_2\cup \ldots \cup A_n [/mm] eine disjunkte Zerlegung von [mm] S_n. [/mm] (Wieso gilt das ?)
Nun ist eigentlich nur noch [mm] |A_i| [/mm] = [mm] f(i)\cdot [/mm] (n-i)! zu begründen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mi 29.04.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
