Anzahl der k-elementigen Teilmengen von M

Question

Die Aufgabe lautet wie folgt:

Seien k, n ∈ N und gelte k ≤ n. Es sei M eine n-elementige Menge. Zeigen
Sie: Die Anzahl der k-elementigen Teilmengen von M ist (n über k).

Also, meine Idee war es jetzt, das ganze mit einer vollständigen Induktion zu zeigen. Undzwar wollte ich das folgendermaßen angehen:

\( \sum\limits_{k=0}^{n}{(n  über k)} \) = (n über n-k)

ich wollte jetzt wissen, ob dieser Beweisvorgang zielführend ist oder nicht :D

wenn nicht, habt ihr eventuell einen Denkanstoß für mich? wäre sehr dankbar :)

Eine andere Idee das ganze anzugehen, wäre z.B. wenn ich ausführlich zeigen würde, wofür n über k steht und wie das ausgeschrieben aussieht, nur ist das Problem, dass die Aufgabe 10 Punkte gibt und das lässt mich irgendwie im Dunkeln umherirren :D

Answer 1

Wenn du k Elemente aus n Elementen auswählen darfst/musst hast du für das

1. Element n Möglichkeiten

2. Element n - 1 Möglichkeiten

3. Element n - 2 Möglichkeiten

...

k. Element n - k + 1 Möglichkeiten

Wenn diese Multipliziert werden hat man

n! / (n - k)!

Da uns die Reihenfolge der k elemente nicht interessiert ist die Anzahl nochmals durch die Reihenfolgen k! zu teilen.

n! / (k! * (n - k)!)

Das ist jetzt aber genau die Definition von (n über k).

Comments

danke dir! :))