Beweisarchiv: Stochastik: Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten

Aus Wikibooks

Beweisarchiv: Stochastik

Statistik: Arithmetisches Mittel zweier Zahlen · Eindeutigkeit der Methode der kleinsten Fehlerquadrate
Wahrscheinlichkeitstheorie: Bernstein-Ungleichung · Satz von Moivre-Laplace · Approximationssatz von Stone-Weierstrass
Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten


mit und ist die Anzahl der -elementigen Teilmengen einer -elementigen Menge.

Beweis[Bearbeiten]

Der Beweis wird durch vollständige Induktion für eine natürliche Zahl erbracht.
Zunächst wird jedoch eine Aussage über das Pascal'sche Dreieck bewiesen.
Das Pascal'sche Dreieck ist eine Form, die Binomialkoeffizienten zweidimensional anzuordnen. Dabei steht an der Spitze des Dreiecks und die anderen Binomialkoeffizienten werden nach unten hin mit wachsenden und von links nach rechts mit wachsenden angeordnet. Dann ergibt sich ein Binomialkoeffizient durch die Summe der beiden darüber, was durch die Formel ausgedrückt wird. Dies kann durch Rechnung eingesehen werden:

Die Umformung erfolgt dabei mit der folgenden Äquivalenz:

Nun führen wir zwei Induktionsanfänge durch. Zunächst sei und , dann gilt

,

was der Aussage entspricht, da nur eine nullelementige Menge existiert, nämlich die leere Menge .
Beim zweiten Induktionsanfang ist , dann folgt

,

was ebenfalls der Aussage entspricht, da als -elementige Teilmenge einer -elementigen Menge nur die Menge selbst in Frage kommt. Damit ist die Aussage also für die beiden „Seiten“ des Pascal'schen Dreiecks gezeigt.
Nun lässt sich induktiv auf alle Binomialkoeffzienten schließen. Sei die Aussage nämlich für und erfüllt, dann ist zunächst einmal . Weiterhin gilt:

  • Der erste Summand gibt die Anzahl der -elementigen Teilmenge in der -elementigen Menge an, also gewissermaßen bevor das „-te Element“ dazukam (keine dieser Teilmengen enthält das -te Element).
  • Der zweite Summand gibt die Anzahl der -elemtigen Teilmengen der -elememtigen Menge an. Gibt man nun das -te Element hinzu, ist dies genau die Anzahl der -elementigen Teilmengenn der -elementigen Menge, die keine Teilmengen der -elementigen Menge sind.

Wikipedia-Verweis[Bearbeiten]