mathproject >> Exkurs: Binomialkoeffizienten und Pascalsches Dreieck

Für

n > 0

ist also n! das fortlaufende Produkt der Zahlen

1,2, \dots, n

. Oft benutzt man die folgende Zerlegungseigenschaft:

(n + 1)! = n! \cdot (n + 1)

Für den Beweis des allgemeinen Binomialtheorems benötigen wir die Eigenschaften 1. und 4. der folgenden Bemerkung.

Bemerkung:

1. $(\begin{matrix} n \\ 0 \end{matrix}) = (\begin{matrix} n \\ n \end{matrix}) = 1$
[5.0.2]

2. $(\begin{matrix} n \\ 1 \end{matrix}) = n für n > 0$
[5.0.3]

3. $(\begin{matrix} n \\ i \end{matrix}) = (\begin{matrix} n \\ n - i \end{matrix})$
[5.0.4]

4. $(\begin{matrix} n \\ i \end{matrix}) + (\begin{matrix} n \\ i - 1 \end{matrix}) = (\begin{matrix} n + 1 \\ i \end{matrix}) für i > 0$
[5.0.5]

Beweis: Wir rechnen jeweils die in der Definition angegebenen Quotienten aus.
1. ► $\frac{n!}{0! \cdot n!} = \frac{n!}{n! \cdot 0!} = 1$

2. ► $\frac{n!}{1! \cdot (n - 1)!} = \frac{(n - 1)! \cdot n}{(n - 1)!} = n$

3. ► $\frac{n!}{i! \cdot (n - i)!} = \frac{n!}{(n - i)! \cdot (n - (n - i))!}$

4. ► $\frac{n!}{i! \cdot (n - i)!} + \frac{n!}{(i - 1)! \cdot (n - i + 1)!}$

$= \frac{n! \cdot (n - i + 1) + n! \cdot i}{i! \cdot (n - i + 1)!}$

$= \frac{n! \cdot (n - i + 1 + i)}{i! \cdot (n - i + 1)!}$

$= \frac{(n + 1)!}{i! \cdot (n + 1 - i)!}$

Die Bedingung

i \leq n

erzwingt, dass es zu jedem n genau n + 1 viele Binomialkoeffizienten gibt. Man errechnet also z.B. für

n = 1 : (\begin{matrix} 1 \\ 0 \end{matrix}) = 1, (\begin{matrix} 1 \\ 1 \end{matrix}) = 1

n = 2 : (\begin{matrix} 2 \\ 0 \end{matrix}) = 1, (\begin{matrix} 2 \\ 1 \end{matrix}) = 2, (\begin{matrix} 2 \\ 2 \end{matrix}) = 1

Schreibt man nun diese Ergebnisse zeilenweise untereinander und richtet die Zeilen dabei zentriert aus, entsteht das bekannte Pascalsche Dreieck, das hier bis zur Zeile n = 4 notiert ist:

Mit Kenntnis der Binomialkoeffizienten lassen sich nun nach dem allgemeinen Binomialtheorem konkrete binomische Formeln aufstellen, etwa für n = 3 und n = 4:

Aus dem allgemeinen Binomialtheorem lassen sich aber noch weitere Eigenschaften der Binomialkoeffizienten ableiten.

Bemerkung:

1. $\sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) = 2^{n}$

[5.0.6]

2. $\sum_{i = 0}^{n} {(- 1)}^{i} (\begin{matrix} n \\ i \end{matrix}) = 0 für n > 0$

[5.0.7]

3. $\sum_{i = m}^{n} (\begin{matrix} i \\ m \end{matrix}) = (\begin{matrix} n + 1 \\ m + 1 \end{matrix}) für m < n$

[5.0.8]

Beweis:

1. ► $2^{n} = {(1 + 1)}^{n} = \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) 1^{n - i} 1^{i} = \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix})$ .

2. ► $0 = {(1 - 1)}^{n} = \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) 1^{n - i} {(- 1)}^{i} = \sum_{i = 0}^{n} {(- 1)}^{i} (\begin{matrix} n \\ i \end{matrix})$ .

3. ►

\begin{array}{l} \sum_{i = m}^{n} (\begin{matrix} i \\ m \end{matrix}) & = (\begin{matrix} m \\ m \end{matrix}) + \sum_{i = m + 1}^{n} (\begin{matrix} i \\ m \end{matrix}) \\ \underset{[5.0.5]}{=} (\begin{matrix} m \\ m \end{matrix}) + \sum_{i = m + 1}^{n} (\begin{matrix} i + 1 \\ m + 1 \end{matrix}) - (\begin{matrix} i \\ m + 1 \end{matrix}) \\ = (\begin{matrix} m \\ m \end{matrix}) - (\begin{matrix} m + 1 \\ m + 1 \end{matrix}) + (\begin{matrix} n + 1 \\ m + 1 \end{matrix}) (Teleskoptrick) \\ = 1 - 1 + (\begin{matrix} n + 1 \\ m + 1 \end{matrix}) = (\begin{matrix} n + 1 \\ m + 1 \end{matrix}) . \end{array}

Auch diese Ergebnisse lassen sich als Eigenschaften des Pascalschen Dreiecks deuten:

Eine wichtige Rolle spielen die Binomialkoeffizienten auch bei kombinatorischen Fragen. Entscheidend ist dabei die folgende Aussage.

Bemerkung:

Jede Menge M mit n Elementen hat genau $(\begin{matrix} n \\ i \end{matrix})$ viele i-elementige Teilmengen:

∣ {N | N \subset M \land ∣ N ∣ = i} ∣ = (\begin{matrix} n \\ i \end{matrix})

[5.0.9]

Beweis: Der Fall i = 0 ist schnell erledigt: M besitzt nur eine Teilmenge mit 0 Elementen, nämlich die leere Menge, so dass die Behauptung aus [5.0.2] folgt. Für $i > 0$ führen wir den Nachweis per Induktion:

$0 \in A :$ Unter der Vorbedingung $i > 0$ ist hier nichts zu zeigen, denn die Voraussetzung $i \leq n$ ist jetzt nicht erfüllbar.
$n \in A \Rightarrow n + 1 \in A :$ Sei jetzt M eine Menge mit n + 1 vielen Elementen, etwa $M = {a_{1}, \dots, a_{n}, a_{n + 1}}$ . Das System der i-elementigen Teilmengen von M zerlegen wir in zwei disjunkte Gruppen:
- Diejenigen N, die $a_{n + 1}$ nicht enthalten. Das sind aber genau alle i-elementigen Teilmengen der n-elementigen Menge ${a_{1}, \dots a_{n}}$ . Nach Induktionsvoraussetzung sind dies $(\begin{matrix} n \\ i \end{matrix})$ viele.
- Diejenigen N, die $a_{n + 1}$ enthalten. Jedem solchen N ordnen wir nun die Menge $N \ {a_{n + 1}}$ zu. Da dies eine bijektive Abbildung in das System der (i − 1)-elementigen Teilmengen von ${a_{1}, \dots a_{n}}$ ist, gibt es in dieser Gruppe genau $(\begin{matrix} n \\ i - 1 \end{matrix})$ viele Mengen.
Insgesamt (siehe [5.0.5]) besitzt M also (T n i )T+(T n i−1 )T=(T n+1 i )T MathType@MTEF@5@5@+=feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrVepeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaaaacaGGPaGaey4kaSIaaiikauaabeqaceaaaeaacaWGUbaabaGaamyAaiabgkHiTiaaigdaaaGaaiykaiabg2da9iaacIcafaqabeGabaaabaGaamOBaiabgUcaRiaaigdaaeaacaWGPbaaaiaacMcaaaa@44EB@ viele i-elementige Teilmengen.

Als Folgerung ergibt sich mit [5.0.6] daraus eine Aussage über die Anzahl aller Teilmengen von M, also über die Mächtigkeit der Potenzmenge von M.

Jede n-elementige Menge M hat genau

\sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) = 2^{n}

viele Teilmengen: