Beweisarchiv: Stochastik: Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten

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

${\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}$ mit $k,n\in \mathbb {N}$ und $n\geq k$ ist die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge.

Beweis

Der Beweis wird durch vollständige Induktion für eine natürliche Zahl $n$ 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 ${\binom {0}{0}}$ an der Spitze des Dreiecks und die anderen Binomialkoeffizienten werden nach unten hin mit wachsenden $n$ und von links nach rechts mit wachsenden $k$ angeordnet. Dann ergibt sich ein Binomialkoeffizient durch die Summe der beiden darüber, was durch die Formel ${\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}$ ausgedrückt wird. Dies kann durch Rechnung eingesehen werden:
${\binom {n+1}{k}}={\frac {(n+1)!}{k!(n+1-k)!}}={\frac {n!}{k!(n-k)!}}{\frac {n+1}{n+1-k}}={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}={\binom {n}{k}}+{\binom {n}{k-1}}$
Die Umformung erfolgt dabei mit der folgenden Äquivalenz:
${\frac {n+1}{n-k+1}}=1+{\frac {k}{n-k+1}}=1+{\frac {k!}{(k-1)!(n-k+1)}}=1+{\frac {k!(n-k)!}{(k-1)!(n-k+1)!}}\Leftrightarrow$${\frac {n!}{k!(n-k)!}}{\frac {n+1}{n-k+1}}={\frac {n!}{k!(n-k)!}}+{\frac {n!}{k!(n-k)!}}{\frac {k!(n-k)!}{(k-1)!(n-k+1)!}}={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}$

Nun führen wir zwei Induktionsanfänge durch. Zunächst sei $n\in \mathbb {N}$ und $k=0$, dann gilt

${\binom {n}{0}}={\frac {n!}{0!(n-0)!}}={\frac {n!}{n!}}=1$,

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

${\binom {n}{n}}={\frac {n!}{n!(n-n)!}}={\frac {n!}{n!}}=1$,

was ebenfalls der Aussage entspricht, da als $n$-elementige Teilmenge einer $n$-elementigen Menge $M$ nur die Menge $M$ 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 ${\binom {n+1}{k}}$ schließen. Sei die Aussage nämlich für ${\binom {n}{k}}$ und ${\binom {n}{k-1}}$ erfüllt, dann ist zunächst einmal ${\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}$. Weiterhin gilt:

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

Wikipedia-Verweis

• Binomialkoeffizient