Unzerlegbare Permutationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:40 Di 26.04.2011 | | Autor: | janisE |
| Aufgabe | Eine Permutation [mm]\sigma = a_1 a_2 \cdots a_n \in S_n[/mm] heißt unzerlegbar, falls gilt:
[mm]\{a_1,\cdots,a_j\} \neq \left [ j \right ] \forall j < n[/mm]
Sei ferner f(n) die Anzahl der unzerlegbaren Permutationen in [mm]S_n[/mm].
Zeigen Sie:
(i) [mm]\sum_{j=1}^{n} = f(j) \cdot (n-j)! = n! \text{ für } n \geq 1 [/mm]
(ii) [mm]\left(\sum_{n \geq 1} f(n) t^n\right) \left(\sum_{n \geq 0} n! t^n\right) = \left(\sum_{n \geq 0} n! t^n\right) - 1[/mm]
Tipp: Koeffizientenvergleich des Cauchy Produktes |
Hallo!
Zuerst möchte ich mich einmla auf die (i) konzentrieren, die ist für mich schon "erschlagend" genug für den Anfang..
Ich habe mir erst einmal die Funktion f(n) angeschaut und die Berechnung für n von 1 bis 4 hingeschrieben. Als Ergebnisse habe ich
f(1) = 0, f(2) = 1, f(3) = 3, f(4) = 13
Eine Regel kann ich nicht erkennen. Prinzipiell müsste ich nun (nach meinem Verständnis) einen Zusammenhang zwischen f(j) und (n-j)! herstellen können, allerdings sehe ich keinen - bis auf die Tatsache, dass alle Permutationen aus [mm]S_i [/mm] mit [mm]\sigma = a_i \cdots[/mm], die also mit dem höchsten Element anfangen unzerlegbar sind. Somit gibt es (i-1)! Permutationen mit Element i vorne. Den Rest konnte ich so leider nicht ableiten.
Könnt ihr mir bitte etwas auf die Sprünge helfen?
Danke im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:57 Di 26.04.2011 | | Autor: | statler |
Hallo!
> Eine Permutation [mm]\sigma = a_1 a_2 \cdots a_n \in S_n[/mm] heißt
> unzerlegbar, falls gilt:
> [mm]\{a_1,\cdots,a_j\} \neq \left [ j \right ] \forall j < n[/mm]
Was soll das bedeuten? Links steht eine Menge und rechts eine natürliche Zahl in eckigen Klammern, das sind für mich zunächst 2 verschiedene Dinge (und deswegen sowieso [mm] $\not=$).
[/mm]
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:12 Di 26.04.2011 | | Autor: | janisE |
> Hallo!
>
> > Eine Permutation [mm]\sigma = a_1 a_2 \cdots a_n \in S_n[/mm] heißt
> > unzerlegbar, falls gilt:
> > [mm]\{a_1,\cdots,a_j\} \neq \left [ j \right ] \forall j < n[/mm]
>
> Was soll das bedeuten? Links steht eine Menge und rechts
> eine natürliche Zahl in eckigen Klammern, das sind für
> mich zunächst 2 verschiedene Dinge (und deswegen sowieso
> [mm]\not=[/mm]).
Hallo Dieter,
tut mir leid, das haben wir vorher definiert. Es gilt einfach
[mm] \left [ n \right ] = \{1,\cdots,n\}[/mm]
Das heißt, dass beispielsweise 2 1 3 zerlegbar (nicht unzerlegbar) ist, weil wenn j = 2, dann ist [mm] \left [ 2 \right ] = \{1,2\} = \{a_1,a_2\} = \{2,1\}[/mm]. Für bspw. 3 1 2 kann kein so ein j gefunden werden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:23 Do 28.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
