0 Daumen
4k Aufrufe

Aufgabe:

Es seien n ∈ N und X eine Menge mit genau n Elementen. Zeigen Sie, dass für k ∈ {0, 1, . . . , n}
die Anzahl der k-elementigen Teilmengen von X gleich dem Binomialkoeffizienten \( \begin{pmatrix} n \\ k \end{pmatrix} \) ist.

Avatar von

2 Antworten

+1 Daumen

Aloha :)

Zu zeigen: Es gibt genau \(\binom{n}{k}\) Möglichkeiten, um aus einer n-elementigen Menge k Elemente auszuwählen.

Induktions-Verankerung bei \(n=0\):

Eine Menge \(M_0\) mit \(n=0\) Elementen ist die leere Menge. Aus dieser Menge kann man genau eine Menge, nämlich die leere Menge an sich, auswählen. Diese hat \(k=0\) Elemente. Tatsächlich ist \(\binom{0}{0}=1\).

Induktions-Verankerung bei \(n=1\):

Aus einer Menge \(M_1\) mit \(n=1\) Element kann man genau eine 0-elementige Menge auswählen, nämlich die leere Menge, und genau eine 1-elementige Menge auswählen, nämlich die Menge \(M_1\) selbst. Tatsächlich gilt: \(\binom{1}{0}=\binom{1}{1}=1\).

Induktionsschritt \(n\to n+1\):

Wir gehen von einer \(n\)-elementigen Menge \(M_n\) aus und fügen ein neues Element hinzu, um eine \((n+1)\)-elementige Menge \(M_{n+1}\) zu erhalten. Wenn wir aus \(M_{n+1}\) nun \(k\) Elemente auswählen wollen, können 2 Fälle unterschieden werden:

1. Fall: Das neue Element wird nicht ausgewählt...

dann müssen \(k\) Elemente aus der Menge \(M_n\) stammen. Dafür gibt es nach Induktionsvoraussetzung \(\binom{n}{k}\) Möglichkeiten.

2. Fall: Das neue Element wird ausgewählt...

dann müssen \((k-1)\) Elemente aus der Menge \(M_n\) stammen. Dafür gibt es nach Induktionsvoraussetzung \(\binom{n}{k-1}\) Möglichkeiten.

Beide Fälle zusammengezählt ergeben:$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$Das ist eine mögiche (rekursive) Definitionsgleichung für den Binomialkoeffizienten. Wenn ihr die in der Vorlesung hattet, bist du jetzt fertig. Falls nicht, musst du ihre Gültigkeit noch zeigen.

Avatar von 152 k 🚀

Das ist die beste und verständlichste Erklärung zur Bedeutung des Binomialkoeffizienten, die mir bekannt ist... Ganz klasse erklärt! Vielen Dank dafür...

0 Daumen

Häufig wird der Binomialkoeffizient als " Anzahl der k-elementigen Teilmengen von einer n-elementigen Menge" definiert.

Das wird bei euch nicht der Fall sein. D.h. du musst erst mal angeben, wie ihr (n tief k) definiert habt. Zudem auch, welche Formeln und Interpretationen ihr benützen dürft.

Avatar von 162 k 🚀

Gleiche Frage schon mal hier https://www.mathelounge.de/55652/anzahl-elementigen-teilmengen-einer-elementigen-menge-gleich

Gefunden durch Verbesserung von Überschrift und Tags.

Die dortige einzige Antwort liefert allerdings im Sinne der Aufgabenstellung absolut nichts.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community