Beweis des Binomialkoeffizienten-

Question

Hey Ihr Lieben,

ich habe folgendes Problem. Ich versuche den folgenden Satz bzw. seinen Beweis nachzuvollziehen und scheitere leider bislang:

Die Anzahl der k–elementigen Teilmengen einer n–elementigen Menge M_n := {m₁, . . . ,m_n} ist gleich (n über k).

Für gewöhnlich beweist man diesen Satz ja mithilfe einer Vollständigen Induktion. Man fängt also z.B. mit n=1, was  den Satz trivialerweise erfüllt.

Sodann kommt der Induktionsschritt: n ↦ n+1.  D.h. wir wollen diesen Satz nun für eine n+1 elementige Menge M_n+1 := {m₁, . . . ,m_n, m_n+1} zeigen.

Induktionsvoraussetzung ist: Die Anzahl der k-elementigen Teilmengen einer n-elementigen Teilmenge ist gleich (n über k).

Für k=0 und k=n+1 ist der Satz ja wieder trivialerweise erfüllt. Wir dürfen also 1 ≤ k ≤ n annehmen.

Nun kommt mein Problem: In jeder Musterlösung, die ich bislang gelesen habe, steht, dass die Menge aller k-elementigen Teilmengen einer n+1 elementigen Menge in zwei Klassen unterteilt ist: Solche, die n+1 enthalten und solche, die n+1 nicht enthalten. Erstere sind gemäß Induktionsvoraussetzung als (n über k-1) darstellbar, letztere gemäß Induktionsvoraussetzung (n über k).

Frage: Wieso lässt sich Letzteres als (n über k) darstellen? Wieso wird aus unserer Grundmenge M_n+1 das Element m_n+1 einfach entfernt? Wir schließen doch nur für k dieses Element aus (sowie das Element m₁)? Ganz grundsätzlich verstehe ich nicht, wieso es eben zwei Klassen sind, in die die Menge aller k-elementigen Teilmengen einer n+1 elementigen Menge unterteilt wird.

Ich bin über jede Hilfe sehr dankbar, bin langsam ein wenig frustriert.

!

Answer 1

Wieso wird aus unserer Grundmenge Mn+1 das Element mn+1 einfach entfernt?

Das tut doch keiner. Es werden hier  nur diejenigen Teilmengen betrachtet, die gerade dieses Element (noch) nicht enthalten.

Machen wir es konkret: Eine Menge mit den 3 Elementen a, b und c  die Teilmengen (ich lasse jetzt die Klammern weg)

leere Menge; a; b; c; ab; ac; ab; abc.

Welche Teilmengen hat dann eine Menge mit den bisherigen Elementen a, b, c und dem zusätzlichen neuen Element d?

Nun, die vorherigen Teilmengen

leere Menge; a; b; c; ab; ac; ab; abc

sind auch Teilmengen unserer neuen (jetzt) vierelementigen Menge.

Durch die Hinzunahme von d kommen aber jetzt noch weitere neue Teilmengen dazu. Das sind alle bisherigen Teilmengen, die zusätzlich noch das Element d erhalten.

Wir hatten z.B. VORHER die drei zweielementigen Teilmengen ab; ac; ab.

Neu dazu kommen zweielementige Teilmengen, die vorher nur einelementig waren und durch Hinzunahme von d zweielementig werden: ad; bd; cd;

Wir hatten z.B. VORHER nur eine dreielementige Teilmenge abc.
Neu dazu kommen dreiielementige Teilmengen, die vorher nur zweielementig waren und durch Hinzunahme von d dreielementig werden: abd; acd; abd;

Wir verallgemeinern: Die Anzahl der jetzt (nach Hinzunahme eines neuen Elements) k-elementigen Teilmengen ist die Summe der Anzahl der vorher schon k-elementigen Teilmengen plus die Anzahl der vorher nur (k-1)-elementigen Teilmengen.

Comments

Vielen, vielen Dank Abakus und Roland, habe es nun endlich verstanden!

Answer 2

Die Anzahl der k–elementigen Teilmengen einer n–elementigen Menge:

Für das erste Element  einer k–elementigen Teilmenge aus einer n–elementigen Menge gibt es n Möglickeiten der Auswahl. Für das zweite zu jeder der n Möglchkeiten noch n-1 Möglichkeiten, für das dritte n-2 Möglichkeiten und so weiter. Für das k-te gibt es n-k+1 Möglichkeiten.Wenn man also die Reihenfolge berücksichtigt, gibt es \( \frac{n!}{(n-k)!} \) Möglichkeiten der Auswahl. Da aber die Reihenfolge der Auswahl keine Rolle spielt, muss man noch durch k! leilen. \( \frac{n!}{k!·(n-k)!} \) schreibt man auch \( \begin{pmatrix} n\\k \end{pmatrix} \) .  

Comments

Vielen, vielen Dank Abakus und Roland, habe es nun endlich verstanden!