Beweisarchiv: Stochastik: 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