geordnete k-partition < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:06 Di 01.02.2011 | | Autor: | hilado |
| Aufgabe | | Anzahl der geordneten k-Paritionen von n ist [mm] \vektor{n - 1 \\ k - 1}. [/mm] |
Diese Frage zielt auf das Verständnis des Beweises an, der hier im Buch steht:
Im Buch wird eine Bijektion von S (der Menge aller geordneten k-Partitionen von n auf die Menge T aller (k-1)-Untermengen in {1, 2, ..., n - 1} konstruiert.
Sei n = [mm] n_1 [/mm] + [mm] n_2 [/mm] + ... + [mm] n_k \in [/mm] S
Wir erklären: f : S -> T durch
[mm] f(n_1 [/mm] + [mm] n_2 [/mm] + ... + [mm] n_k) [/mm] = [mm] \{n_1, n_1 + n_2, ..., n_1 + ... n_{k-1}\}
[/mm]
Jetzt kommt eigentlich schon meine erste Frage: Warum wird hier bis [mm] n_{k-1} [/mm] die Menge genommen und nicht bis [mm] n_{k}, [/mm] das ist mir noch nicht ganz ersichtlich :(
|
|
| |
|
> Anzahl der geordneten k-Paritionen von n ist [mm]\vektor{n - 1 \\
k - 1}.[/mm]
>
> Diese Frage zielt auf das Verständnis des Beweises an, der
> hier im Buch steht:
>
> Im Buch wird eine Bijektion von S (der Menge aller
> geordneten k-Partitionen von n auf die Menge T aller
> (k-1)-Untermengen in {1, 2, ..., n - 1} konstruiert.
>
> Sei n = [mm]n_1[/mm] + [mm]n_2[/mm] + ... + [mm]n_k \in[/mm] S
>
> Wir erklären: f : S -> T durch
> [mm]f(n_1[/mm] + [mm]n_2[/mm] + ... + [mm]n_k)[/mm] = [mm]\{n_1, n_1 + n_2, ..., n_1 + ... n_{k-1}\}[/mm]
>
> Jetzt kommt eigentlich schon meine erste Frage: Warum wird
> hier bis [mm]n_{k-1}[/mm] die Menge genommen und nicht bis [mm]n_{k},[/mm]
> das ist mir noch nicht ganz ersichtlich :(
Hallo,
wenn ich mir das Rotmarkierte anschaue, dann ist es jedenfalls richtig, daß auf der rechten Seite der Definitionsgleichung eine (k-1)-elementige Menge steht.
Und das Argument von f ist eine geordnete k-Partition von n.
Du fragst Dich jetzt, warum das [mm] n_k [/mm] nicht mit verwurstet wird.
Wenn [mm] n_1, [/mm] ..., [mm] n_{k-1} [/mm] festliegen, ist damit auch das [mm] n_k [/mm] bestimmt, denn es ist [mm] n_k= n-(n_1+...+n_{k-1}). [/mm] Für [mm] n_k [/mm] hat man keine Wahl.
Damit hängt es zusammen, daß es so gmacht wird, wie's gemacht wird.
Gruß v. Angela
|
|
|
|
