Binomialkoeffizient < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:31 Mo 31.08.2009 | | Autor: | hilado |
| Aufgabe | Zeigen Sie für alle m, r, k [mm] \in [/mm] N durch kombinatorische Überlegungen:
1. [mm] \vektor{m \\ r} [/mm] * [mm] \vektor{r \\ k} [/mm] = [mm] \vektor{m \\ k} [/mm] * [mm] \vektor{m - k \\ r - k} [/mm] |
Ich hab da ehrlich gesagt keinen großen Peil, wie ich diese Frage beantworten soll. Durch den Binomialkoeffizienten stimmt alles (ist ja aber nicht gefragt).
Ich habs versucht mit Bildern zu zeichen, doch die haben mir nicht die Frage beantwortet warum gerade [mm] \vektor{m - k \\ r - k}
[/mm]
Ich habs auch mal ganz pragmatisch versucht: [mm] \vektor{m \\ r} [/mm] ist die Anzahl der Teilmengen der Mächtigkeit r einer m-elementigen Menge und dasselbe dann auch mit [mm] \vektor{r \\ k}, [/mm] aber da bin ich leider auch auf keinen grünen Zweig gekommen ...
Hat jemand einen Tipp wie ich auf die Lösung kommen kann?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:41 Mo 31.08.2009 | | Autor: | felixf |
Hallo!
> Zeigen Sie für alle m, r, k [mm]\in[/mm] N durch kombinatorische
> Überlegungen:
>
> 1. [mm]\vektor{m \\ r}[/mm] * [mm]\vektor{r \\ k}[/mm] = [mm]\vektor{m \\ k}[/mm] *
> [mm]\vektor{m - k \\ r - k}[/mm]
> Ich hab da ehrlich gesagt keinen
> großen Peil, wie ich diese Frage beantworten soll. Durch
> den Binomialkoeffizienten stimmt alles (ist ja aber nicht
> gefragt).
>
> Ich habs versucht mit Bildern zu zeichen, doch die haben
> mir nicht die Frage beantwortet warum gerade [mm]\vektor{m - k \\ r - k}[/mm]
>
> Ich habs auch mal ganz pragmatisch versucht: [mm]\vektor{m \\ r}[/mm]
> ist die Anzahl der Teilmengen der Mächtigkeit r einer
> m-elementigen Menge und dasselbe dann auch mit [mm]\vektor{r \\ k},[/mm]
> aber da bin ich leider auch auf keinen grünen Zweig
> gekommen ...
Schau dir diese zwei Mengen an:
[mm] $\mathcal{X} [/mm] := [mm] \{ (A, B) \mid B \subseteq A, A \subseteq \{ 1, \dots, m \}, |A| = r, |B| = k \}$
[/mm]
[mm] $\mathcal{Y} [/mm] := [mm] \{ (B, A') \mid B \subseteq \{ 1, \dots, m \}, |B| = k, A' \subseteq \{ 1, \dots, m \} \setminus B, |A'| = r - k \}$
[/mm]
Beachte, dass die Abbildung [mm] $\mathcal{X} \to \mathcal{Y}$, [/mm] $(A, B) [mm] \mapsto [/mm] (B, A [mm] \setminus [/mm] B)$ eine Bijektion ist.
LG Felix
|
|
|
|
