Deine Meinung zählt – Gestalte unsere Lerninhalte mit!
Wir entwickeln neue, interaktive Formate für die Hochschulmathematik. Nimm dir maximal 15 Minuten Zeit, um an unserer Umfrage teilzunehmen.
Mit deinem Feedback machen wir die Mathematik für dich und andere Studierende leichter zugänglich!
In diesem Kapitel stelle ich dir die wichtigsten Eigenschaften des Binomialkoeffizienten vor.
Es sei im Folgendem
k
{\displaystyle k}
und
n
{\displaystyle n}
eine natürliche Zahl, wobei
k
{\displaystyle k}
und
n
{\displaystyle n}
hier auch Null sein dürfen. Außerdem sei
0
≤
k
≤
n
{\displaystyle 0\leq k\leq n}
. Es gelten nun folgende Regeln:
(
n
0
)
=
1
{\displaystyle {\binom {n}{0}}=1}
(
n
n
)
=
1
{\displaystyle {\binom {n}{n}}=1}
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}
k
⋅
(
n
k
)
=
n
⋅
(
n
−
1
k
−
1
)
{\displaystyle k\cdot {\binom {n}{k}}=n\cdot {\binom {n-1}{k-1}}}
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}
für
0
≤
k
<
n
{\displaystyle 0\leq k<n}
Einige der obigen Gleichungen können gut aus der Anschauung des Binomialkoeffizienten erklärt werden, dass
(
n
k
)
{\displaystyle {\binom {n}{k}}}
der Anzahl der
k
{\displaystyle k}
-elementigen Teilmengen einer
n
{\displaystyle n}
-elementigen Menge entspricht:
(
n
n
)
=
1
{\displaystyle {\binom {n}{n}}=1}
weil eine
n
{\displaystyle n}
-elementige Menge
M
{\displaystyle M}
nur eine
n
{\displaystyle n}
-elementige Teilmenge enthält (nämlich die Menge
M
{\displaystyle M}
).
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}
. Zu jeder Teilmenge von
M
{\displaystyle M}
mit
k
{\displaystyle k}
Elementen existiert deren Komplement, welches
n
−
k
{\displaystyle n-k}
Elemente enthält. Somit ist die Anzahl der unterschiedlichen Teilmengen gleich.
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}
. Stellen wir uns Mengen
M
,
M
′
:=
M
∪
{
e
}
{\displaystyle M,M':=M\cup \{e\}}
vor, wobei
|
M
|
=
n
{\displaystyle |M|=n}
und
e
{\displaystyle e}
ein zuvor nicht in
M
{\displaystyle M}
enthaltenes Element ist. Dann ist der erste Summand die Anzahl der
k
{\displaystyle k}
-elementigen Teilmengen von
M
{\displaystyle M}
- fügt man aber jeder dieser Mengen das neue Element
e
{\displaystyle e}
hinzu, sind diese nun
k
+
1
{\displaystyle k+1}
-elementige Teilmengen von
M
′
{\displaystyle M'}
. Zusammen mit den
k
+
1
{\displaystyle k+1}
-elementigen Teilmengen ohne
e
{\displaystyle e}
(der zweite Summand), erhalten wir das Ergebnis.
Andere Rechenregeln sind aber nicht so offensichtlich. Hier kann im Beweis auf die Fakultätsdefinition
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\tfrac {n!}{k!(n-k)!}}}
des Binomialkoeffizienten zurückgegriffen werden.
Originale Version von Blaise Pascal
Der Mathematiker Blaise Pascal
Das pascalsche Dreieck ist eine grafische Anordnung der Binomialkoeffizienten in einem Dreieck:
(
0
0
)
(
1
0
)
(
1
1
)
(
2
0
)
(
2
1
)
(
2
2
)
(
3
0
)
(
3
1
)
(
3
2
)
(
3
3
)
⋮
{\displaystyle {\begin{array}{c}{\binom {0}{0}}\\{\binom {1}{0}}\quad {\binom {1}{1}}\\{\binom {2}{0}}\quad {\binom {2}{1}}\quad {\binom {2}{2}}\\{\binom {3}{0}}\quad {\binom {3}{1}}\quad {\binom {3}{2}}\quad {\binom {3}{3}}\\\vdots \end{array}}}
Wenn man die Binomialkoeffizienten ausrechnet, dann ergibt sich folgendes Dreieck:
1
1
1
1
2
1
1
3
3
1
⋮
{\displaystyle {\begin{array}{c}1\\1\quad 1\\1\quad 2\quad 1\\1\quad 3\quad 3\quad 1\\\vdots \end{array}}}
Die Regel
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}
ermöglicht es, den Binomialkoeffizienten als Summe der beiden direkt oberhalb liegenden Binomialkoeffizienten zu berechnen:
Animation zur Erstellung des Pascalschem Dreieck
Das Besondere am pascalschen Dreieck ist, dass man an ihm direkt die Binomalkoeffizienten und damit die Vorfaktoren beim Ausklammern von Potenzen der Form
(
x
+
y
)
n
{\displaystyle (x+y)^{n}}
ablesen kann. Beispielsweise lautet die Zeile für
n
=
3
{\displaystyle n=3}
:
1
3
3
1
{\displaystyle {\color {Red}1}\quad {\color {Orange}3}\quad {\color {OliveGreen}3}\quad {\color {Blue}1}}
Dies ist die vierte Zeile, weil die erste Zeile im Dreieck zu
n
=
0
{\displaystyle n=0}
gehört. Damit wissen wir ohne Nachrechnen:
(
x
+
y
)
3
=
1
⋅
x
3
+
3
⋅
x
2
y
+
3
⋅
x
y
2
+
1
⋅
y
3
{\displaystyle (x+y)^{3}={\color {Red}1}\cdot x^{3}+{\color {Orange}3}\cdot x^{2}y+{\color {OliveGreen}3}\cdot xy^{2}+{\color {Blue}1}\cdot y^{3}}
Der Sinn des pascalschen Dreiecks ist es also, die Vorfaktoren beim Ausklammern von Potenzen der Form
(
x
+
y
)
n
{\displaystyle (x+y)^{n}}
einfach ablesen zu können. Das Dreieck wurde im Übrigen nach Blaise Pascal benannt, der es 1655 in einem seiner Bücher veröffentlichte. Es wurde aber bereits früher von anderen Mathematikern eingesetzt[ 1] .
Satz
Es gelten die beiden Formeln
(
n
0
)
=
1
{\displaystyle {\binom {n}{0}}=1}
und
(
n
n
)
=
1
{\displaystyle {\binom {n}{n}}=1}
.
Beweis
Die obigen Gleichungen ergeben sich durch Ausnutzung der Fakultätsdefinition
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\tfrac {n!}{k!(n-k)!}}}
des Binomialkoeffizienten:
(
n
0
)
=
n
!
0
!
⋅
(
n
−
0
)
!
=
n
!
1
⋅
n
!
=
1
{\displaystyle {\binom {n}{0}}={\frac {n!}{0!\cdot (n-0)!}}={\frac {n!}{1\cdot n!}}=1}
und
(
n
n
)
=
n
!
n
!
⋅
(
n
−
n
)
!
=
n
!
n
!
⋅
0
!
=
n
!
n
!
⋅
1
=
1
{\displaystyle {\binom {n}{n}}={\frac {n!}{n!\cdot (n-n)!}}={\frac {n!}{n!\cdot 0!}}={\frac {n!}{n!\cdot 1}}=1}
Satz
Es ist
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}
.
Beweis
Die Formel kann folgendermaßen bewiesen werden:
(
n
k
)
=
n
!
k
!
⋅
(
n
−
k
)
!
=
n
!
(
n
−
k
)
!
⋅
k
!
=
n
!
(
n
−
k
)
!
⋅
(
n
−
n
+
k
)
!
=
n
!
(
n
−
k
)
!
⋅
(
n
−
(
n
−
k
)
)
!
=
(
n
n
−
k
)
{\displaystyle {\begin{aligned}{\binom {n}{k}}&={\frac {n!}{k!\cdot (n-k)!}}\\&={\frac {n!}{(n-k)!\cdot k!}}\\&={\frac {n!}{(n-k)!\cdot (n-n+k)!}}\\&={\frac {n!}{(n-k)!\cdot (n-(n-k))!}}\\&={\binom {n}{n-k}}\end{aligned}}}
Satz
Es ist
k
⋅
(
n
k
)
=
n
⋅
(
n
−
1
k
−
1
)
{\displaystyle k\cdot {\binom {n}{k}}=n\cdot {\binom {n-1}{k-1}}}
.
Wie kommt man auf den Beweis?
Zunächst können wir beide Binomialkoeffizienten ausschreiben:
k
⋅
(
n
k
)
=
k
⋅
n
!
k
!
⋅
(
n
−
k
)
!
n
⋅
(
n
−
1
k
−
1
)
=
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
1
−
(
k
−
1
)
)
!
{\displaystyle {\begin{aligned}k\cdot {\binom {n}{k}}&=k\cdot {\frac {n!}{k!\cdot (n-k)!}}\\n\cdot {\binom {n-1}{k-1}}&=n\cdot {\frac {(n-1)!}{(k-1)!\cdot (n-1-(k-1))!}}\end{aligned}}}
Beide erhaltene Terme können soweit wie möglich vereinfacht werden:
k
⋅
n
!
k
!
⋅
(
n
−
k
)
!
=
n
!
(
k
−
1
)
!
⋅
(
n
−
k
)
!
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
1
−
(
k
−
1
)
)
!
=
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
k
)
!
=
n
!
(
k
−
1
)
!
⋅
(
n
−
k
)
!
{\displaystyle {\begin{aligned}k\cdot {\frac {n!}{k!\cdot (n-k)!}}&={\frac {n!}{(k-1)!\cdot (n-k)!}}\\n\cdot {\frac {(n-1)!}{(k-1)!\cdot (n-1-(k-1))!}}&={\frac {n\cdot (n-1)!}{(k-1)!\cdot (n-k)!}}\\&={\frac {n!}{(k-1)!\cdot (n-k)!}}\end{aligned}}}
Die vereinfachten Terme stimmen überein, also müssen auch
k
⋅
(
n
k
)
{\displaystyle k\cdot {\binom {n}{k}}}
und
n
⋅
(
n
−
1
k
−
1
)
{\displaystyle n\cdot {\binom {n-1}{k-1}}}
identisch sein. Im Beweis müssen wir nun die verwendeten Termumformungen aufschreiben, mit denen
k
⋅
(
n
k
)
{\displaystyle k\cdot {\binom {n}{k}}}
in
n
⋅
(
n
−
1
k
−
1
)
{\displaystyle n\cdot {\binom {n-1}{k-1}}}
umgeformt werden kann.
Beweis
Es ist
k
⋅
(
n
k
)
=
k
⋅
n
!
k
!
⋅
(
n
−
k
)
!
=
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
k
)
!
=
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
1
−
k
+
1
)
!
=
n
⋅
(
n
−
1
)
!
(
k
−
1
)
!
⋅
(
n
−
1
−
(
k
−
1
)
)
!
=
n
⋅
(
n
−
1
k
−
1
)
{\displaystyle {\begin{aligned}k\cdot {\binom {n}{k}}&=k\cdot {\frac {n!}{k!\cdot (n-k)!}}\\&=n\cdot {\frac {(n-1)!}{(k-1)!\cdot (n-k)!}}\\&=n\cdot {\frac {(n-1)!}{(k-1)!\cdot (n-1-k+1)!}}\\&=n\cdot {\frac {(n-1)!}{(k-1)!\cdot (n-1-(k-1))!}}\\&=n\cdot {\binom {n-1}{k-1}}\end{aligned}}}
Satz
Sei
k
,
n
∈
N
{\displaystyle k,n\in \mathbb {N} }
mit
0
≤
k
<
n
{\displaystyle 0\leq k<n}
. Es ist dann
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}
.
Wie kommt man auf den Beweis?
Zum Beweis der Gleichung
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}
gehen wir schrittweise vor:
Frage: Wie lautet die zu beweisende Gleichung, nachdem man auf beiden Seiten die Definition
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\tfrac {n!}{k!(n-k)!}}}
eingesetzt hat?
(
n
+
1
)
!
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
n
!
k
!
⋅
(
n
−
k
)
!
+
n
!
(
k
+
1
)
!
⋅
(
n
−
k
−
1
)
!
{\displaystyle {\frac {(n+1)!}{(k+1)!\cdot (n-k)!}}={\frac {n!}{k!\cdot (n-k)!}}+{\frac {n!}{(k+1)!\cdot (n-k-1)!}}}
Aufgabe: Versuche durch Termumformungen die gerade gefundene Gleichung zu beweisen.
n
!
k
!
⋅
(
n
−
k
)
!
+
n
!
(
k
+
1
)
!
⋅
(
n
−
k
−
1
)
!
↓
Brüche gleichnamig machen
=
n
!
⋅
(
k
+
1
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
+
n
!
⋅
(
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
n
!
⋅
(
k
+
1
)
+
n
!
⋅
(
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
↓
Zähler zusammenfassen
=
n
!
⋅
(
k
+
1
+
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
n
!
⋅
(
n
+
1
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
(
n
+
1
)
!
(
k
+
1
)
!
⋅
(
n
−
k
)
!
{\displaystyle {\begin{aligned}&{\frac {n!}{k!\cdot (n-k)!}}+{\frac {n!}{(k+1)!\cdot (n-k-1)!}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ {\text{Brüche gleichnamig machen}}\right.}\\[0.5em]=\ &{\frac {n!\cdot (k+1)}{(k+1)!\cdot (n-k)!}}+{\frac {n!\cdot (n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {n!\cdot (k+1)+n!\cdot (n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ {\text{Zähler zusammenfassen}}\right.}\\[0.5em]=\ &{\frac {n!\cdot (k+1+n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {n!\cdot (n+1)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {(n+1)!}{(k+1)!\cdot (n-k)!}}\end{aligned}}}
Beweis
Es ist
(
n
k
)
+
(
n
k
+
1
)
=
n
!
k
!
⋅
(
n
−
k
)
!
+
n
!
(
k
+
1
)
!
⋅
(
n
−
k
−
1
)
!
↓
Brüche gleichnamig machen
=
n
!
⋅
(
k
+
1
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
+
n
!
⋅
(
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
n
!
⋅
(
k
+
1
)
+
n
!
⋅
(
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
↓
Zähler zusammenfassen
=
n
!
⋅
(
k
+
1
+
n
−
k
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
n
!
⋅
(
n
+
1
)
(
k
+
1
)
!
⋅
(
n
−
k
)
!
=
(
n
+
1
)
!
(
k
+
1
)
!
⋅
(
n
−
k
)
!
↓
Im Nenner
+
1
−
1
einfügen
=
(
n
+
1
)
!
(
k
+
1
)
!
⋅
(
(
n
+
1
)
−
(
k
+
1
)
)
!
=
(
n
+
1
k
+
1
)
{\displaystyle {\begin{aligned}&{\binom {n}{k}}+{\binom {n}{k+1}}\\[0.5em]=\ &{\frac {n!}{k!\cdot (n-k)!}}+{\frac {n!}{(k+1)!\cdot (n-k-1)!}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ {\text{Brüche gleichnamig machen}}\right.}\\[0.5em]=\ &{\frac {n!\cdot (k+1)}{(k+1)!\cdot (n-k)!}}+{\frac {n!\cdot (n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {n!\cdot (k+1)+n!\cdot (n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ {\text{Zähler zusammenfassen}}\right.}\\[0.5em]=\ &{\frac {n!\cdot (k+1+n-k)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {n!\cdot (n+1)}{(k+1)!\cdot (n-k)!}}\\[0.5em]=\ &{\frac {(n+1)!}{(k+1)!\cdot (n-k)!}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ {\text{Im Nenner}}+1-1{\text{ einfügen}}\right.}\\[0.5em]=\ &{\frac {(n+1)!}{(k+1)!\cdot ((n+1)-(k+1))!}}\\[0.5em]=\ &{\binom {n+1}{k+1}}\end{aligned}}}