Stirlingzahlen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:20 Sa 19.02.2011 | | Autor: | hilado |
| Aufgabe | Es bezeichne [mm] s_{n,k}, [/mm] 1 <= k <= n, die Anzahl von Zerlegungen der Zahlenmenge [mm] \{1, ..., n \} [/mm] in k disjunkte, nicht-leere Teilmengen. (Beispiel: [mm] \{1, 2, 3 \} [/mm] = [mm] \{1\} \cup \{2, 3\} [/mm] = [mm] \{ 2 \} \cup \{ 1, 3 \} [/mm] = [mm] \{ 3 \} \cup \{ 1, 2 \}, [/mm] also [mm] s_{2,3} [/mm] = 3.) Zeigen Sie, dass die [mm] s_{n, k} [/mm] folgende Rekursion erfüllen:
[mm] s_{n, k} [/mm] = [mm] s_{n - 1, k - 1} [/mm] + k * [mm] s_{n - 1, k} [/mm] |
Hallo Leute,
ich hab einen Anfang aber ich weiß nicht wie ich den Rest beweisen soll:
Wir nehmen ein festes Element a aus der n-Menge. Diese kann alleine vorkommen als eine Menge mit einem Element und zwar a. D.h. wir müssen nun n - 1 Elemente in k - 1 diskunkte Mengen zerlegen. Oder das Element a ist in einer Menge mit anderen Elementen. Dann müssen wir noch n - 1 Elemente in k disjunkte Mengen zerlegen.
Soweit bin ich, aber wie erkläre ich nun das k vor den [mm] s_{n - 1, k} [/mm] ?
|
|
| |
|
Hallo,
> Es bezeichne [mm]s_{n,k},[/mm] 1 <= k <= n, die Anzahl von
> Zerlegungen der Zahlenmenge [mm]\{1, ..., n \}[/mm] in k disjunkte,
> nicht-leere Teilmengen. (Beispiel: [mm]\{1, 2, 3 \}[/mm] = [mm]\{1\} \cup \{2, 3\}[/mm]
> = [mm]\{ 2 \} \cup \{ 1, 3 \}[/mm] = [mm]\{ 3 \} \cup \{ 1, 2 \},[/mm] also
> [mm]s_{2,3}[/mm] = 3.) Zeigen Sie, dass die [mm]s_{n, k}[/mm] folgende
> Rekursion erfüllen:
>
> [mm]s_{n, k}[/mm] = [mm]s_{n - 1, k - 1}[/mm] + k * [mm]s_{n - 1, k}[/mm]
Ich rede hier im folgenden mal von k- Partitionen einer n elementigen Menge.
> Hallo
> Leute,
>
> ich hab einen Anfang aber ich weiß nicht wie ich den Rest
> beweisen soll:
>
> Wir nehmen ein festes Element a aus der n-Menge. Diese kann
> alleine vorkommen als eine Menge mit einem Element und zwar
> a. D.h. wir müssen nun n - 1 Elemente in k - 1 diskunkte
> Mengen zerlegen. Oder das Element a ist in einer Menge mit
> anderen Elementen. Dann müssen wir noch n - 1 Elemente in
> k disjunkte Mengen zerlegen.
Ok.
>
> Soweit bin ich, aber wie erkläre ich nun das k vor den
> [mm]s_{n - 1, k}[/mm] ?
Wir betrachten das gleiche Element [mm] a_n=a [/mm] aus dem anderen Fall. In diesem Fall ist [mm] $a_n\in T_i$ [/mm] mit [mm] $|T_i|>1$ ($T_i\subset\{a_1,a_2,\ldots,a_n\}$ [/mm] eine Teilmenge).
Es gibt insgesamt k Teilmengen (da wir ja [mm] S_{n,k} [/mm] betrachten) in jeder k- Partition. Der entscheidende Schritt ist nun, dass [mm] $T_1, \ldots, T_{i-1},T_i\backslash\{a\}, T_{i+1}, \ldots, T_k$ [/mm] eine k-1 Partition der n-1 Elemente [mm] a_1, \ldots, a_{n-1} [/mm] ist. Für das Element [mm] a_n [/mm] gibt es jedoch k Einfügepositionen, daher der Faktor k.
Die rekursive Formel ergibt sich aus der Summe der beiden Fälle, da sie unabhängig sind.
Gruß
EDIT: Siehe durchgestrichenes. Das war ein Tippfehler.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:17 So 20.02.2011 | | Autor: | hilado |
> Der entscheidende
> Schritt ist nun, dass [mm]T_1, \ldots, T_{i-1},T_i\backslash\{a\}, T_{i+1}, \ldots, T_k[/mm]
> eine k-1 Partition der n-1 Elemente [mm]a_1, \ldots, a_{n-1}[/mm]
> ist.
Sicher dass du k-1 Partition meinst und nicht k-Partition? Nur weil wir aus einer menge [mm] T_{i} [/mm] ein Element a rausnehmen, ist diese Menge ja nicht leer (weil ja [mm] |T_{i}| [/mm] > 1 ist) und wir ja deshalb immer noch eine k-Partition haben?
|
|
|
| |
|
Hi,
> > Der entscheidende Schritt ist nun, dass [mm]T_1, \ldots, T_{i-1},T_i\backslash\{a\}, T_{i+1}, \ldots, T_k[/mm]
> > eine k-1 Partition der n-1 Elemente [mm]a_1, \ldots, a_{n-1}[/mm] ist.
>
> Sicher dass du k-1 Partition meinst und nicht k-Partition?
Danke, dass war ein Tippfehler. Es handelt sich natürlich um eine k Partition der n-1 Elemente. Das ist ja auch das Ziel (siehe Rekursionsformel). Habs editiert.
Gruß
|
|
|
|
