1.4 Kombinatorik (Fortsetzung: Pascalsches Dreieck)
Den oben schon angegebenen Binomischen Satz könnte man nun mit dem Summenzeichen etwas knapper also so schreiben:
Für eine beliebige natürliche Zahl \(n\in \mathbb {N}\) gilt:
\((a+b)^n=\sum\limits_{k=0}^n\left(\begin{array}{c}n\\k\end{array}\right)a^{n-k}b^k\)
Für die Binomialkoeffizienten gibt es einige wichtige Regeln:
-
\({n \choose k} = {n \choose n-k}\)
-
\({n+1 \choose k} = {n \choose k} + {n \choose k-1}\)
Beide Formeln lassen sich recht anschaulich begründen:
-
\({n \choose k} = {n \choose n-k}\) gilt, da es auf das Gleiche herauskommt, ob man \(k\) Zahlen aus \(n\) auswählt oder \(n-k\) der \(n\) Zahlen nicht auswählt.
-
\({n+1 \choose k}\) ist die Anzahl der Möglichkeiten, \(k\) Zahlen aus \(n+1\) auszuwählen. Diese ergibt sich als Summe aus den Anzahlen der Möglichkeiten
-
noch \(\mathbf{k-1}\) aus den restlichen \(\mathbf{n}\) Zahlen \(\{ 2,3,\dots ,n+1\} \) auszuwählen, wenn man die Zahl \(\mathbf{1}\) schon ausgewählt hat und
-
\(\mathbf{k}\) aus den \(\mathbf{n}\) Zahlen \(\{ 2,3,\dots ,n+1\} \) auszuwählen, falls man \(\mathbf{1}\) nicht ausgewählt hat.
-
\(\begin{align*}\left(\begin{array}{c}6\\3\end{array}\right)&=\displaystyle\frac{6\cdot5\cdot4}{1\cdot2\cdot 3}=20\\\left(\begin{array}{c}40\\38\end{array}\right)&={40\choose2}=\displaystyle\frac{40\cdot 39}{1\cdot 2}=780\end{align*}\)
\(\begin{align*}\left(\begin{array}{c}7\\5\end{array}\right)&=\left(\begin{array}{c}7\\2\end{array}\right)=\displaystyle\frac{7\cdot 6}{1\cdot 2}=21\\ \left(\begin{array}{c}15\\5\end{array}\right)&=\displaystyle\frac{15\cdot14\cdot 13\cdot12\cdot11}{1\cdot2\cdot3\cdot 4\cdot5}=3003\end{align*}\)
Und hier noch ein paar Beispiele zum Selbermachen:
Das Pascalsche Dreieck
Zur Berechnung von Binomialkoeffizienten kann man die zweite Eigenschaft benutzen, die sich auf elegante Art im Pascalschen Dreieck wiederfindet.
\(\begin{array}{ccccccccccccc}&&&&&&{0\choose0}&&&&&&\\&&&&&{1\choose0}&&{1\choose1}&&&&&\\&&&&{2\choose0}&&{2\choose1}&&{2\choose2}&&&&\\&&&{3\choose0}&&{3\choose1}&&{3\choose2}&&{3\choose3}&&&\\&&{4\choose0}&&{4\choose1}&&{4\choose2}&&{4\choose3}&&{4\choose4}&&\\&{5\choose0}&&{5\choose1}&&{5\choose2}&&{5\choose3}&&{5\choose4}&&{5\choose5}&\\\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\ddots\end{array}\)
Die Gleichung \({n+1 \choose k} = {n \choose k} + {n \choose k-1}\) hat hier zur Folge, dass jeder Binomialkoeffizient die Summe der beiden (links und rechts) über ihm stehenden ist.
Man wendet also das folgende Rechenschema an:
\(\begin{array}{ccccccccccccccccc}&&&&&&&&1&&&&&&&&\\&&&&&&&\swarrow&&\searrow&&&&&&&\\&&&&&&1&&&&1&&&&&&\\&&&&&\swarrow&&\searrow&&\swarrow&&\searrow&&&&&\\&&&&1&&&&2&&&&1&&&&\\&&&\swarrow&&\searrow&&\swarrow&&\searrow&&\swarrow&&\searrow&&&\\&&1&&&&3&&&&3&&&&1&&\\&\swarrow&&\searrow&&\swarrow&&\searrow&&\swarrow&&\searrow&&\swarrow&&\searrow&\\1&&&&4&&&&6&&&&4&&&&1\\\vdots&&&&\vdots&&&&\vdots&&&&\vdots&&&&\vdots\end{array}\)
Die Berechnung von Binomialkoeffizienten mit dem Pascalschen Dreieck hat allerdings einen Nachteil: Um beispielsweise \({50 \choose 23}\) zu berechnen, muss man vorher schon sehr viele andere Binomialkoeffzienten berechnen.
Benutzt man dagegen die Formel \({n\choose k}=\frac{n!}{k!(n-k)!}\), dann können die Terme \(n!\), \(k!\) und \((n-k)!\), die man dafür verwendet, sehr viel größer sein als das Endergebnis. Für Binomialkoeffizienten \({n\choose k}\) mit großem \(n\) und \(k\), wie sie in der Wahrscheinlichkeitstheorie gelegentlich auftreten, gibt es die Stirlingsche Formel \(n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\), mit der man Fakultäten \(n!\) und Binomialkoeffizienten \({n\choose k}\) zwar nicht exakt berechnen kann, aber mit wesentlich weniger Aufwand einen doch recht genauen Näherungswert bestimmen kann.
-
Ein paar Zeilen vom Pascalschen Dreieck mehr:
\(\begin{array}{ccccccccccccccccc}&&&&&&&&1&&&&&&&&\\&&&&&&&1&&1&&&&&&&\\&&&&&&1&&2&&1&&&&&&\\&&&&&1&&3&&3&&1&&&&&\\&&&&1&&4&&6&&4&&1&&&&\\&&&1&&5&&10&&10&&5&&1&&&\\&&1&&6&&15&&20&&15&&6&&1&&\\&1&&7&&21&&35&&35&&21&&7&&1&\\1&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&1\end{array}\)
Bemerkung:Eine nette Graphik kann man am Computer erzeugen, indem man alle geraden Zahlen im Pascalschen Dreieck durch ein weißes Kästchen und alle ungeraden Zahlen durch ein schwarzes Kästchen ersetzt.
Weiter zu den komplexen Zahlen