Beweisarchiv: Stochastik: Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!\cdot (n-k)!}$ mit $k,n\in \mathbb{N}$ und $n\ge 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 $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})$ ausgedrückt wird. Dies kann durch Rechnung eingesehen werden:
$(\genfrac{}{}{0ex}{}{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)!}=(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{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)!}\iff$$\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

$(\genfrac{}{}{0ex}{}{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 $\mathrm{\varnothing }$.
Beim zweiten Induktionsanfang ist $k=n$, dann folgt

$(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n+1}{k})$ schließen. Sei die Aussage nämlich für $(\genfrac{}{}{0ex}{}{n}{k})$ und $(\genfrac{}{}{0ex}{}{n}{k-1})$ erfüllt, dann ist zunächst einmal $(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{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