Binomialkoeffizient

Bedeutung, Schreibweise und Definition

Der Binomialkoeffizient zählt, auf wie viele Arten man aus einer Menge von n verschiedenen Objekten genau k Objekte auswählt, ohne zurückzulegen und ohne die Reihenfolge zu beachten. Er ist damit die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge. Diese Grundaufgabe der Kombinatorik ist unter anderem für Lottoziehungen wichtig.

Man schreibt \binom{n}{k} und spricht „n über k“, „k aus n“ oder „n tief k“. Auf Taschenrechnern steht dafür oft nCr („n choose r“). Für ganze Zahlen 0\leq k\leq n gilt die Definition \binom{n}{k}=\frac{n!}{k!\,(n-k)!}, wobei k! die Fakultät bezeichnet. Für k>n ist \binom{n}{k}:=0.

Die Bezeichnung kommt daher, dass diese Zahlen im binomischen Lehrsatz als Koeffizienten der Potenz von x+y auftreten: (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k.

Rechnen und Pascalsches Dreieck

Durch Kürzen der Fakultäten erhält man geeignete Produktformen: \binom{n}{k}=\frac{n(n-1)\dotsm(n-k+1)}{k!}=\prod_{j=1}^{k}\frac{n+1-j}{j}. Binomialkoeffizienten sind stets nichtnegative ganze Zahlen. Wichtige Sonderfälle sind \binom n0=\binom nn=1 und \binom n1=\binom n{n-1}=n. Außerdem gelten \binom nk=\frac{n-k+1}{k}\binom n{k-1},\qquad k\binom nk=n\binom{n-1}{k-1} und die Symmetrie \binom nk=\binom n{n-k}. Zum Beispiel ist \binom53=\binom52=10.

Die Rekursionsformel lautet \binom{n+1}{k+1}=\binom nk+\binom n{k+1}. Sie bildet das Pascalsche Dreieck: An der k-ten Stelle der n-ten Zeile, jeweils ab Null gezählt, steht \binom nk. Jede innere Zahl ist die Summe der beiden Zahlen darüber. Damit lassen sich alle Koeffizienten bis zu einer vorgegebenen Zeile bestimmen.

Für eine effiziente Einzelberechnung wird wegen der Symmetrie bei k>n/2 zuerst k durch n-k ersetzt und dann die Produktform schrittweise ausgewertet. Dabei bleiben die Zwischenergebnisse natürliche Zahlen. Ohne solche Kürzung wären bei Fakultäten schon die Rechenkapazitäten oft für n=69 erschöpft, da 69!<10^{100}<70!. Im Unterschied dazu zählt P(n,r)=n!/(n-r)! bei nPr auch die Reihenfolgen der r Elemente mit und teilt daher nicht durch r!.

Kombinatorische Deutung und Beispiele

Die Formel \binom nk lässt sich dadurch erklären, dass es zunächst n!/(n-k)! geordnete k-Tupel ohne Wiederholung gibt. Jede ungeordnete k-elementige Teilmenge wird dabei k!-mal gezählt, nämlich in allen Anordnungen ihrer Elemente. Die Division durch k! liefert deshalb n!/[k!(n-k)!].

Gleichwertig kann man eine n-elementige Menge in eine ausgewählte k-elementige Teilmenge und ihre n-k-elementige Ergänzung zerlegen. Dies erklärt zugleich \binom nk=\binom n{n-k}. Die Rekursionsformel kann kombinatorisch bewiesen werden: Für ein festes Element x zerfallen die k-elementigen Teilmengen in diejenigen, die x enthalten, und diejenigen, die x nicht enthalten. Ihre Anzahlen sind \binom{n-1}{k-1} beziehungsweise \binom{n-1}{k}.

Beim deutschen Lotto „6 aus 49“ gibt es \binom{49}{6}=13.983.816\approx14 Millionen mögliche Tipps. Genau sechs Richtige sind mit einem bestimmten Tipp auf genau eine Weise möglich. Für r Richtige gibt es \binom6r\binom{43}{6-r} Tipps; die Wahrscheinlichkeit lautet \binom6r\binom{43}{6-r}/\binom{49}{6}. So ergeben sich für fünf Richtige 6\cdot43=258 Tipps und für null Richtige \binom{43}{6}=6.096.454, also etwa 44 % aller Tipps.

Bei einer Ziehung aus a roten, b grünen und c blauen Murmeln ist die Wahrscheinlichkeit, genau d rote, e grüne und f blaue Murmeln zu ziehen, P=\frac{\binom ad\binom be\binom cf}{\binom{a+b+c}{d+e+f}}. Für 4 rote, 5 grüne und 6 blaue Murmeln sowie eine Ziehung von 1 roten, 2 grünen und 3 blauen unter insgesamt sechs Murmeln ist P=160/1001.

Summen, Identitäten und weitere Anwendungen

Die Summe aller Binomialkoeffizienten einer Zeile beträgt \sum_{k=0}^{n}\binom nk=2^n. Kombinatorisch zählt dies alle Teilmengen einer n-elementigen Menge; aus dem binomischen Lehrsatz folgt die Formel durch x=y=1. Für n>0 gilt die alternierende Summe \sum_{k=0}^{n}(-1)^k\binom nk=0, erhältlich durch x=1, y=-1. Daher haben Teilmengen gerader und ungerader Größe jeweils die Anzahl 2^{n-1}.

Weitere zentrale Identitäten sind \sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1} und die Vandermondesche Identität \sum_{j=0}^{k}\binom mj\binom n{k-j}=\binom{m+n}{k}. Letztere zählt k-elementige Teilmengen einer Menge aus m roten und n grünen Kugeln nach der Anzahl j der roten Kugeln. Für k=m=n folgt \sum_{j=0}^{n}\binom nj^2=\binom{2n}{n}, der mittlere Binomialkoeffizient. Die Hockey-Stick-Identität lautet für n,r\in\mathbb N, n\ge r: \sum_{i=r}^{n}\binom ir=\binom{n+1}{r+1}.

Binomialkoeffizienten stellen auch Fibonacci-Zahlen dar, etwa F_{2n+1}=\sum_{k=0}^{n}\binom{n+k}{2k} und F_{2n+2}=\sum_{k=0}^{n}\binom{n+k+1}{2k+1}. In der Geometrie besitzt ein n-dimensionales reguläres Simplex \binom{n+1}{k+1} k-dimensionale Grenzelemente. Ein n-dimensionaler Hyperwürfel besitzt \binom nk2^{n-k} k-dimensionale Hyperwürfel, ein Kreuzpolytop 2^{k+1}\binom n{k+1} k-dimensionale Simplizes.

Für eine Primzahl p gilt ferner \binom{n_0+pn_1}{k_0+pk_1}\equiv\binom{n_0}{k_0}\binom{n_1}{k_1}\pmod p, wenn n_0,k_0\in\{0,\dotsc,p-1\} und n_1,k_1\in\mathbb N. Damit lässt sich der Koeffizient modulo p anhand der Ziffern zur Basis p berechnen.

Verallgemeinerungen in der Analysis

In der Analysis wird der allgemeine Binomialkoeffizient für eine beliebige komplexe Zahl \alpha und ganzzahliges k definiert durch \binom\alpha k=\begin{cases}\dfrac{\alpha(\alpha-1)\dotsm(\alpha-(k-1))}{k!},&k>0,\\1,&k=0,\\0,&k<0.\end{cases} Für nichtnegative ganzzahlige \alpha stimmt dies mit der kombinatorischen Definition überein. Beispielsweise ist \binom{2{,}5}{2}=1{,}875, und \binom{-1}{k}=(-1)^k. Mit Gammafunktion \Gamma und Betafunktion \mathrm B lässt sich auch der zweite Eintrag verallgemeinern: \binom\alpha z=\frac{\Gamma(\alpha+1)}{\Gamma(z+1)\Gamma(\alpha-z+1)}=\frac1{(\alpha+1)\mathrm B(z+1,\alpha-z+1)}. Dabei gilt \binom\alpha z=\binom\alpha{\alpha-z}; ist z oder \alpha-z eine negative ganze Zahl, ist der Wert 0.

Diese Koeffizienten erscheinen in binomischen Reihen, insbesondere \sum_{k=0}^{\infty}\binom\alpha k z^k=(1+z)^\alpha unter den angegebenen Konvergenzbedingungen. Für höhere Ableitungen gilt die verallgemeinerte Produktregel (u\cdot v)^{(n)}=\sum_{k=0}^{n}\binom nk u^{(k)}v^{(n-k)}.

Die Gammafunktion besitzt die Gaußsche Produktdarstellung \Gamma(z)=\lim_{n\to\infty}\frac{n^z n!}{z(z+1)(z+2)\dotsm(z+n)}. Außerdem verknüpfen Binomialkoeffizienten harmonische Zahlen mit der Digammafunktion: \sum_{k=1}^{n}\binom nk(-1)^{k-1}/k=H_n=\psi(n+1)+\gamma. Schließlich liefert die kontinuierliche Definition im zentralen Grenzwertsatz \lim_{n\to\infty}\frac{\binom{2n^2}{n^2+nx}}{\binom{2n^2}{n^2}}=\exp(-x^2), die Gaußsche Glockenkurvenfunktion.