Doppelte Abzählen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:53 Mo 21.02.2011 | | Autor: | hilado |
| Aufgabe | Zeigen Sie mit der Regel vom doppelten Abzählen, dass für positive ganze Zahlen n >= k >= 1 die folgende Identität gilt:
k * [mm] \vektor{n \\ k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1 }
[/mm]
Hinweis: Die angegebenen Zahlgrößen, sagen wir [mm] a_{n, k} [/mm] beschreiben die Anzahl k-elementiger Teilmengen einer n-elementigen Menge, wobei eines der k Elemente gesondert ausgezeichneten ist. Beispiel: Für n = 3, k = 2 sind dies die Mengen
[mm] \{1*, 2 \}, \{1, 2* \},
[/mm]
[mm] \{1*, 3 \}, \{1, 3* \},
[/mm]
[mm] \{2*, 3 \}, \{2, 3* \},
[/mm]
wobei * das ausgezeichnete Element kennzeichnet. Also ist [mm] a_{3, 2} [/mm] = 6. |
Also, ich hab die Lösung hier stehen, doch leider verstehe ich diese nicht ganz:
Paar bestehend aus einer Menge und einem darin ausgezeichneten Element, können wir auf zwei Weisen abzählen:
* Wir wählen die Teilmenge und zeichnen darin eines der Elemente aus:
[mm] a_{n, k} [/mm] = [mm] \vektor{n \\ k }*k
[/mm]
Frage: Wie begründe ich das k an dieser Stelle? Warum gerade k?
* Wir wählen das Element, das als ausgezeichnetes auftreten soll, und ergänzen aus den verbleibenden n - 1 Elementen zu einer k-Teilmenge:
[mm] a_{n, k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1}.
[/mm]
Das kann ich schon eher nachvollziehen. Wenn wir eine Menge haben [mm] \{ n_{1}, n_{2}, ..., n_{k} \} (n_{k} [/mm] ist dabei das ausgezeichnete Element), dann kann ich das für jedes Element so schreiben:
[mm] \{ n_{k} \} \cup \{n_{1}, n_{2}, ..., n_{n-1} \}
[/mm]
Da wir [mm] n_{k} [/mm] aus der Teilmenge k-ter Ordnung rausgenommen haben, müssen wir nur noch die Teilmengen k-1-ter Ordnung der Menge n-1 zählen.
Nach der Regel vom doppelten Abzählen erhalten wir:
k * [mm] \vektor{n \\ k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1}
[/mm]
|
|
| |
|
Hallo,
> Zeigen Sie mit der Regel vom doppelten Abzählen, dass für
> positive ganze Zahlen n >= k >= 1 die folgende Identität
> gilt:
>
> k * [mm]\vektor{n \\ k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1 }[/mm]
>
> Hinweis: Die angegebenen Zahlgrößen, sagen wir [mm]a_{n, k}[/mm]
> beschreiben die Anzahl k-elementiger Teilmengen einer
> n-elementigen Menge, wobei eines der k Elemente gesondert
> ausgezeichneten ist. Beispiel: Für n = 3, k = 2 sind dies
> die Mengen
>
> [mm]\{1*, 2 \}, \{1, 2* \},[/mm]
> [mm]\{1*, 3 \}, \{1, 3* \},[/mm]
> [mm]\{2*, 3 \}, \{2, 3* \},[/mm]
>
> wobei * das ausgezeichnete Element kennzeichnet. Also ist
> [mm]a_{3, 2}[/mm] = 6.
> Also, ich hab die Lösung hier stehen, doch leider
> verstehe ich diese nicht ganz:
>
> Paar bestehend aus einer Menge und einem darin
> ausgezeichneten Element, können wir auf zwei Weisen
> abzählen:
>
> * Wir wählen die Teilmenge und zeichnen darin eines der
> Elemente aus:
>
> [mm]a_{n, k}[/mm] = [mm]\vektor{n \\ k }*k[/mm]
>
> Frage: Wie begründe ich das k an dieser Stelle? Warum
> gerade k?
Es gibt [mm] \vektor{n \\ k } [/mm] k-elementige Teilmengen (Binomialkoeffizient). Da in jeder Teilmenge k Elemente sind, gibt es k Möglichkeiten, eines davon auszuzeichnen.
>
> * Wir wählen das Element, das als ausgezeichnetes
> auftreten soll, und ergänzen aus den verbleibenden n - 1
> Elementen zu einer k-Teilmenge:
>
> [mm]a_{n, k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1}.[/mm]
>
> Das kann ich schon eher nachvollziehen. Wenn wir eine Menge
> haben [mm]\{ n_{1}, n_{2}, ..., n_{k} \} (n_{k}[/mm] ist dabei das
> ausgezeichnete Element), dann kann ich das für jedes
> Element so schreiben:
>
> [mm]\{ n_{k} \} \cup \{n_{1}, n_{2}, ..., n_{n-1} \}[/mm]
>
> Da wir [mm]n_{k}[/mm] aus der Teilmenge k-ter Ordnung rausgenommen
> haben, müssen wir nur noch die Teilmengen k-1-ter Ordnung
> der Menge n-1 zählen.
>
>
>
> Nach der Regel vom doppelten Abzählen erhalten wir:
>
> k * [mm]\vektor{n \\ k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1}[/mm]
>
Gruß
|
|
|
|
