Fakultät und Binomialkoeffizient sind Konzepte, die eigentlich aus der Kombinatorik stammen, die aber auch in der Analysis unverzichtbar ist. Beide sind wichtige Zählkoeffizienten, d. h. sie geben die Kardinalität bestimmter Mengen an. In dieser Blog-Folge lernen wir ihre Definition kennen.
Fakultät
Die Fakultät von $n$ ist nichts anderes als das Produkt der ersten $n$ natürlichen Zahlen.
Definition
Für $n \in \N_0$ heißt das Produkt \[ n! := \prod_{k=1}^n k = 1\cdot 2 \cdot \ldots \cdot n \] Fakultät von $n$. Wir setzen $0! = 1$.
Beispiel
\begin{eqnarray*} 3! & = & 1 \cdot 2 \cdot 3 = 6 \\ 4! & = & 1 \cdot 2 \cdot 3 \cdot 4 = 24 \\ 5! & = & 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 \end{eqnarray*}In der Vorlesung werde ich an dieser Stelle oft gefragt, warum man $0! = 1$ setzt und nicht etwa $0! = 0$. Der Grund hierfür ist, dass für $n=0$ das Produkt \[ \prod_{k=1}^n k, \] ein sogenanntes leeres Produkt ist, also aus keinem einzigen Faktor besteht, und ein leeres Produkt in der Mathematik immer den Wert $1$ hat. Und warum hat nun ein leeres Produkt immer den Wert $1$? Weil $1$ das neutrale Element der Multiplikation ist! Ein leeres Produkt soll sich neutral verhalten, also anschaulich so, als wäre es gar nicht als Faktor präsent. Bei der Multiplikation gelingt uns dies mit der $1$ und nicht mit der $0$. Die $0$ ist dagegen das neutrale Element der Addition, und dementsprechend hat eine leere Summe auch immer den Wert $0$, aber bei der Fakultät wird multipliziert und nicht addiert. Also: $0! = 1$.
Die Fakultät gibt beispielsweise an, wie viele verschiedene Anordnungen es für $n$ Objekte gibt. Deshalb wird die Fakultät häufig in der Kombinatorik und der Wahrscheinlichkeitstheorie verwendet. Im Rahmen der Analysis werden wir der Fakultät insbesondere bei Potenz- und Taylorreihen wieder begegnen.
Beispiel
Hier ein Beispiel zu der Anzahl verschiedener Anordnungen für $n$ Objekte. Wie schon erwähnt beträgt sie $n!$. Betrachten wir beispielsweise die Objekte $a, b, c$, dann gibt es somit $3! = 6$ verschiedene Anordnungen für $a, b, c$, die ich hier aufliste: \[ \begin{array}{ccc} a & b & c \\ a & c & b \\ b & a & c \\ b & c & a \\ c & a & b \\ c & b & a \end{array} \] Dementsprechend gibt es für vier Objekte $4! = 24$ verschiedene Anordnungen und für fünf Objekte $5! = 120$ verschiedene Anordnungen.Das nächste Beispiel macht deutlich, dass die Fakultät eine extrem stark wachsende Funktion in $n$ ist.
Beispiel
\begin{eqnarray*} 5! & = & 120 \\ 10! & = & 3628800 \\ 20! & = & 2432902008176640000 \\ 30! & = & 265252859812191058636308480000000 \approx 2.65 \cdot 10^{32} \end{eqnarray*}Hier ein weiteres kleines Beispiel, um das starke Wachstum der Fakultätsfunktion zu veranschaulichen: Man schätzt, dass die Gesamtanzahl aller Atome des Universums zwischen $10^{80}$ und $10^{82}$ liegt. Diese Größenordnung erreichen wir schon mit $60!$. Es gilt: \[ 60! \approx 8.3209 \cdot 10^{81}. \]
Die Stirlingformel
Die bekannte Stirlingformel gibt das asymptotische Verhalten der Fakultät an. Es gilt \[ n! \sim \sqrt{2\pi n} \left( \frac{n}{\e} \right)^n. \] Mit Python können wir der Stirlingformel leicht auf den Zahn fühlen.
import math
n = 60
fak = math.factorial(n)
approx = math.sqrt(2 * math.pi * n) * (n/math.e) ** n
prozfehler = (fak - approx) / fak * 100
print(prozfehler)
Ausgabe:
0.13879119878704682
Die Stirlingformel liefert demnach für $60!$ eine Schätzung, die nur ein wenig mehr
als 0.1% vom korrekten Wert für die Fakultät abweicht.
Du kanst auch gerne das Python-Skript für andere Werte von n ausprobieren.
Dann wirst Du feststellen, dass die Stirlingformel auch schon für kleine n
eine recht gute Approximation der Fakultät liefert.
Binomialkoeffizient
Ein weiterer Zählkoeffizient, der für die Analysis von großer Bedeutung ist, ist der Binomialkoeffizient. Er enthält in seiner Definition auch wieder die Fakultät.Definition
Sei $n, k \in \N_0$. Dann heißt der Ausdruck \[ \binom{n}{k} := \frac{n (n-1) \cdot \ldots \cdot (n-k+1)}{k!} \] Binomialkoeffizient von $n$ über $k$.Wir betrachten zunächst einige Beispiele mit besonderen Werten für $n$ oder $k$.
Für $k=0$ entsteht im Zähler der Definition des Binomialkoeffizienten ein leeres Produkt, also $1$. Im Nenner steht $0!$ und damit wieder $1$. Also gilt \[ \binom{n}{0} = 1 \] für alle $n \in \N_0$. Beachte, dass dies auch für $n=0$ gilt, also \[ \binom{0}{0} = 1. \] Für $k=1$ steht im Zähler $n$ und im Nenner $1! = 1$. Demnach gilt \[ \binom{n}{1} = n \] für alle $n \in \N_0$.
Für $n=k$ steht sowohl im Nenner als auch im Zähler $n!$. Somit gilt \[ \binom{n}{n} = 1 \] für alle $n\in\N_0$.
Gilt $k > n$, dann entsteht im Zähler $0$ als einer der Faktoren. Daher gilt \[ \binom{n}{k} = 0 \] für alle $k,n \in \N_0$ mit $k > n$.
Für $k \leq n$ können wir den Binomialkoeffizienten auch in der Form \[ \binom{n}{k} = \frac{n!}{k! (n-k)!} \] schreiben, denn \begin{eqnarray*} \binom{n}{k} & = & \frac{n (n-1) \cdot \ldots \cdot (n-k+1)}{k!} \\ & = & \frac{n (n-1) \cdot \ldots \cdot (n-k+1)}{k!} \cdot \frac{(n-k)(n-k-1)\cdot\ldots\cdot 1}{(n-k)(n-k-1)\cdot\ldots\cdot 1} \\ & = & \frac{n!}{k!(n-k)!}. \end{eqnarray*} Wenn Du die Wahl zwischen den beiden Formeln hast, dann solltest Du immer diejenige wählen, die für Deine Berechung einfacher oder praktischer ist.
Als Zählkoeffizient liefert der Binomialkoeffizient beispielsweise die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge.
Beispiel
Wir betrachten die Menge $M = \{a,b,c,d,e\}$, also eine Menge mit fünf Elementen. Wie viele dreielementige Teilmengen hat $M$? Die Antwort ist \[ \binom{5}{3} = \frac{5\cdot 4\cdot 3}{3!} = \frac{5\cdot 4\cdot 3}{1 \cdot 2 \cdot 3} = \frac{5\cdot 4}{1\cdot 2} = \frac{20}{2} = 10. \] Also hat $M$ zehn verschiedene dreielementige Teilmengen, die ich hier mal alle aufliste: \begin{aligned} & \{a,b,c\} \\ & \{a,b,d\} \\ & \{a,b,e\} \\ & \{a,c,d\} \\ & \{a,c,e\} \\ & \{a,d,e\} \\ & \{b,c,d\} \\ & \{b,c,e\} \\ & \{b,d,e\} \\ & \{c,d,e\} \end{aligned}Für das Rechnen mit Binomialkoeffizienten sind die folgenden Formeln äußerst hilfreich.
Proposition
Für $n,k \in\N$ mit $k\leq n$ gilt:
- \[ \binom{n}{k} = \binom{n}{n-k} \]
- \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
Beweis
- \begin{eqnarray*} \binom{n}{k} & = & \frac{n!}{k!(n-k)!} \\[2ex] & = & \frac{n!}{(n-(n-k))! (n-k)!} \\[2ex] & = & \frac{n!}{(n-k)! (n-(n-k))!} \\[2ex] & = & \binom{n}{n-k} \end{eqnarray*} Zur Erläuterung: Wir schreiben $k!$ als $(n-(n-k))!$. Dann vertauschen wir im Nenner die beiden Faktoren und erhalten damit genau die Defintion für $\binom{n}{n-k}$.
- Wenn wir eine Gleichung beweisen wollen, besteht der erste Schritt des Beweises darin zu entscheiden, auf welcher Seite der Gleichung wir anfangen. Wenn wir hier auf der rechten Seite der Gleichung anfangen, dann sind die nächsten Schritte klar bestimmt, denn die Binomialkoeffizienten sind Brüche und Brüche können wir addieren. Wenn wir dagegen mit der linken Seite beginnen würden, ist zunächst mal völlig unklar, was wir mit dem einzelnen Binomialkoeffizienten machen sollten. Also fangen wir rechts an. \begin{eqnarray*} \binom{n-1}{k-1} + \binom{n-1}{k} & = & \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} + \frac{(n-1)!}{k!(n-1-k)!} \\[2ex] & = & \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} \\[2ex] & = & \frac{(n-1)!\cdot k}{k!(n-k)!} + \frac{(n-1)!\cdot(n-k)}{k!(n-k)!} \\[2ex] & = & \frac{(n-1)!\cdot k + (n-1)!\cdot(n-k)}{k!(n-k)!} \\[2ex] & = & \frac{(n-1)!\cdot (k+n-k)}{k!(n-k)!} \\[2ex] & = & \frac{(n-1)!\cdot n}{k! (n-k)!} \\[2ex] & = & \frac{n!}{k! (n-k)!} \\[2ex] & = & \binom{n}{k} \end{eqnarray*} Zur Erläuterung: Wir schreiben die Binomialkoeffizienten als Brüche und machen diese Brüche dann gleichnamig, indem wir den ersten Bruch mit $k$ erweitern und den zweiten Bruch mit $n-k$. Dann fassen wir die beiden Brüche zu einem Bruch zusammen. Die anschließenden Termumformungen im Zähler liefern uns dann das gewünschte Ergebnis.
Im Beispiel oben hatte ich schon erwähnt, dass $\binom{n}{k}$ die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge ist. Mit der Additionsformel (ii) aus der letzten Proposition können wir dies leicht begründen. Dies demonstriere ich im Beweis des folgenden Satzes.
Satz
Für alle $k,n \in \N_0$ gilt: Eine $n$-elementige Menge hat $\binom{n}{k}$ verschiedene Teilmengen.Beweis
Zunächst machen wir uns darüber Gedanken, wie wir den Beweis genau führen. Es sei \[ C_{n,k} := \text{Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge}. \] Damit müssen wir nun \[ \forall n\in\N_0 \forall k\in\N_0 : C_{n,k} = \binom{n}{k} \] beweisen. Da wir eine allquantifizierte Aussage über die natürlichen Zahlen haben, bietet sich hier die vollständige Induktion als Beweismethode an. Aber über welche der beiden Parameter, $n$ oder $k$, führen wir die Induktion? Der Trick besteht darin, sich für einen zu entscheiden und damit eine allquantifizerte Aussage über den anderen Paramter zu beweisen. Für uns bedeutet dies, dass wir die Induktion über $n$ führen und für jedes $n$ zeigen, dass die innere Aussage \[ \forall k\in\N_0: C_{n,k} = \binom{n}{k} \] wahr ist.
$n=0$: Eine $0$-elementige Menge kann nur die leere Menge sein. Die leere Menge hat genau eine Teilmenge, nämlich die leere Menge selbst. Also gilt \[ C_{0,0} = 1 = \binom{0}{0} \] und für alle $k>0$ \[ C_{0,k} = 0 = \binom{0}{k}. \] Damit ist der Induktionsanfang bewiesen.
$n-1\rightarrow n$: Eine Teilmenge einer $n$-elementigen Menge kann auch höchsten $n$ Elemente umfassen. Somit gilt schon mal für alle $k > n$: \[ C_{n,k} = 0 = \binom{n}{k}. \] Somit müssen wir nur noch den Fall $k\leq n$ untersuchen.
O. B. d. A. sei die $n$-elementige Menge $\{1,2,\ldots,n\}$. Ansonsten könnten wir die Elemente der Menge mit den Zahlen $1$ bis $n$ indizieren und die gleiche folgende Argumentation mit den Indizes der Elemente durchführen.
Es sei nun $M$ eine beliebige $k$-elementige Teilmenge von $\{1,2,\ldots,n\}$. Wir machen eine Fallunterscheidung.
- Es gelte $n \notin M$. Dann ist $M$ eine $k$-elementige Teilmenge von $\{1,\ldots,n-1.\}$ Nach Induktionsvoraussetzung gibt es $\binom{n-1}{k}$ viele solcher Teilmengen.
- Es gilt $n\in M$. Dann ist $M\setminus\{n\}$ eine $k-1$-elementige Teilmenge von $\{1,\ldots,n-1\}$. Nach Induktionsvoraussetzung gibt es $\binom{n-1}{k-1}$ viele solcher Teilmengen.
Binomialkoeffizienten treten auch im Binomischen Lehrsatz, den wir in der nächsten Blog-Folge behandeln, wieder auf. Der Binomische Lehrsatz verallgemeinert die aus der Schule bekannten Binomischen Formeln.
Teilen und Drucken