Binomialkoeffizient

Die Binomialkoeffizienten können so angeordnet werden, dass sie ein Pascalsches Dreieck bilden, bei dem jeder Eintrag die Summe der beiden unmittelbar darüber liegenden ist. ⓘ

Visualisierung der Binomialentwicklung bis zur 4. Potenz ⓘ

In der Mathematik sind die Binomialkoeffizienten die positiven ganzen Zahlen, die als Koeffizienten im Binomischen Lehrsatz vorkommen. Üblicherweise wird ein Binomialkoeffizient durch ein Paar von ganzen Zahlen n ≥ k ≥ 0 indiziert und geschrieben ${\tbinom {n}{k}}.$ Er ist der Koeffizient des Terms xk in der Polynomentwicklung der binomischen Potenz (1 + x)n; dieser Koeffizient lässt sich durch die multiplikative Formel

${\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},$

berechnet werden, die unter Verwendung der Fakultätsschreibweise kompakt ausgedrückt werden kann als ⓘ

${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$ ⓘ

Zum Beispiel ist die vierte Potenz von 1 + x

${\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}$

und der Binomialkoeffizient ${\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6$ ist der Koeffizient des Terms x². ⓘ

Anordnen der Zahlen ${\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}$ in aufeinanderfolgenden Zeilen für $n=0,1,2,\ldots$ ergibt eine dreieckige Anordnung, das so genannte Pascalsche Dreieck, das die Rekursionsbeziehung erfüllt

${\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.$ ⓘ

Die Binomialkoeffizienten kommen in vielen Bereichen der Mathematik vor, insbesondere in der Kombinatorik. Das Symbol ${\tbinom {n}{k}}$ wird in der Regel als "n wähle k" gelesen, denn es gibt ${\tbinom {n}{k}}$ Möglichkeiten gibt, eine (ungeordnete) Teilmenge von k Elementen aus einer festen Menge von n Elementen auszuwählen. Zum Beispiel gibt es ${\tbinom {4}{2}}=6$ Möglichkeiten, 2 Elemente aus $\{1,2,3,4\},$ nämlich $\{1,2\},\,\{1,3\},\,\{1,4\},\,\{2,3\},\,\{2,4\},$ und $\{3,4\}.$ ⓘ

Die Binomialkoeffizienten können verallgemeinert werden zu ${\tbinom {z}{k}}$ für jede komplexe Zahl z und jede ganze Zahl k ≥ 0 verallgemeinert werden, und viele ihrer Eigenschaften bleiben auch in dieser allgemeineren Form erhalten. ⓘ

Der Binomialkoeffizient ist eine mathematische Funktion, mit der sich eine der Grundaufgaben der Kombinatorik lösen lässt. Er gibt an, auf wie viele verschiedene Arten man aus einer Menge von $n$ verschiedenen Objekten jeweils $k$ Objekte auswählen kann (ohne Zurücklegen und ohne Beachtung der Reihenfolge). Der Binomialkoeffizient ist also die Anzahl der $k$-elementigen Teilmengen in der Potenzmenge einer $n$-elementigen Grundmenge. ⓘ

„49 über 6“ in Deutschland bzw. „45 über 6“ in Österreich und der Schweiz ist z. B. die Anzahl der möglichen Ziehungen beim Lotto (ohne Berücksichtigung der Zusatzzahl). ⓘ

Ein Binomialkoeffizient hängt von zwei natürlichen Zahlen $n$ und $k$ ab. Er wird mit dem Symbol

${\binom {n}{k}}$

geschrieben und als „n über k“, „k aus n“ oder „n tief k“ gesprochen. Die englische Abkürzung nCr für n choose r findet sich als Beschriftung auf Taschenrechnern. ⓘ

Eine Erweiterung des aus der Kombinatorik stammenden Binomialkoeffizienten stellt der allgemeine Binomialkoeffizient dar, der in der Analysis verwendet wird. ⓘ

Geschichte und Notation

Andreas von Ettingshausen führte die Notation ${\tbinom {n}{k}}$ im Jahr 1826 ein, obwohl die Zahlen schon Jahrhunderte zuvor bekannt waren (siehe Pascalsches Dreieck). Die früheste bekannte ausführliche Erörterung der Binomialkoeffizienten findet sich in einem Kommentar von Halayudha aus dem zehnten Jahrhundert zu einem alten Sanskrit-Text, Pingalas Chandaḥśāstra. Die zweitfrüheste Beschreibung von Binomialkoeffizienten stammt von Al-Karaji. Um 1150 gab der indische Mathematiker Bhaskaracharya in seinem Buch Līlāvatī eine Erklärung der Binomialkoeffizienten. ⓘ

Zu den alternativen Schreibweisen gehören C(n, k), nCk, nCk, Ckn, Cnk und C_n,k, bei denen das C für Kombinationen oder Auswahlmöglichkeiten steht. Viele Taschenrechner verwenden Varianten der C-Notation, weil sie diese auf einem einzeiligen Display darstellen können. In dieser Form lassen sich die Binomialkoeffizienten leicht mit k-Vermutungen von n vergleichen, geschrieben als P(n, k) usw. ⓘ

Definition und Interpretationen

k n	0	1	2	3	4	⋯ ⓘ
0	1	0	0	0	0	⋯
1	1	1	0	0	0	⋯
2	1	2	1	0	0	⋯
3	1	3	3	1	0	⋯
4	1	4	6	4	1	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋱
Die ersten paar Binomialkoeffizienten in einem linksbündigen Pascalschen Dreieck

Für die natürlichen Zahlen (einschließlich 0) n und k kann der Binomialkoeffizient ${\tbinom {n}{k}}$ als der Koeffizient des Monoms Xk in der Erweiterung von (1 + X)n definiert werden. Der gleiche Koeffizient kommt auch (wenn k ≤ n) in der binomischen Formel vor

$(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}$

(∗)

(gültig für beliebige Elemente x, y eines kommutativen Rings), was den Namen "Binomialkoeffizient" erklärt. ⓘ

Ein weiteres Vorkommen dieser Zahl ist in der Kombinatorik zu finden, wo sie die Anzahl der Möglichkeiten angibt, auf die k Objekte unter n Objekten ausgewählt werden können, ohne Berücksichtigung der Reihenfolge; genauer gesagt, die Anzahl der k-Element-Teilmengen (oder k-Kombinationen) einer n-Element-Menge. Diese Zahl kann als gleich derjenigen der ersten Definition angesehen werden, unabhängig von den nachstehenden Formeln zu ihrer Berechnung: Wenn man in jedem der n Faktoren der Potenz (1 + X)n den Term X vorübergehend mit einem Index i (von 1 bis n) bezeichnet, dann ergibt jede Teilmenge von k Indizes nach der Expansion einen Beitrag Xk, und der Koeffizient dieses Monoms im Ergebnis ist die Anzahl solcher Teilmengen. Dies zeigt insbesondere, dass ${\tbinom {n}{k}}$ eine natürliche Zahl für beliebige natürliche Zahlen n und k ist. Es gibt viele andere kombinatorische Interpretationen von Binomialkoeffizienten (Zählprobleme, bei denen die Antwort durch einen Binomialkoeffizientenausdruck gegeben ist), z. B. ist die Anzahl der aus n Bits (Ziffern 0 oder 1) gebildeten Wörter, deren Summe k ist, gegeben durch ${\tbinom {n}{k}}$, während die Anzahl der Schreibweisen $k=a_{1}+a_{2}+\cdots +a_{n}$ wobei jedes ai eine nichtnegative ganze Zahl ist, ist gegeben durch ${\tbinom {n+k-1}{n-1}}$. Die meisten dieser Interpretationen lassen sich leicht als Äquivalent zum Zählen von k-Kombinationen betrachten. ⓘ

Für ganzzahlige $n$ existiert ein effizienter Algorithmus, der die Produktformel

${n \choose k}=\prod _{i=1}^{k}{\frac {n+1-i}{i}}$

des Binomialkoeffizienten anwendet. Auf Grund des stetigen Wechsels zwischen Multiplikation und Division wachsen die Zwischenergebnisse nicht unnötig an. Zusätzlich sind auch alle Zwischenergebnisse natürliche Zahlen. ⓘ

Um unnötigen Rechenaufwand zu vermeiden, berechnet man im Fall $k>n/2$ den Binomialkoeffizienten:

${n \choose n-k}={n \choose k}$ ⓘ

Der folgende Pseudocode verdeutlicht die Berechnung:

binomialkoeffizient(n, k)
1  wenn 2*k > n dann k = n-k
2  ergebnis = 1
3  für i = 1 bis k
4      ergebnis = ergebnis * (n + 1 - i) / i
5  rückgabe ergebnis ⓘ

Diese Rechenmethode nutzen auch Taschenrechner, wenn sie die Funktion anbieten. Sonst wäre die Rechenkapazität (oftmals für $n=69$) erschöpft. Die Beschriftung der Funktionstaste mit nCr beschreibt die Reihenfolge der Eingabewerte in Infixnotation; zunächst Anzahl der Elemente n, dann die Funktionstaste Combinations, dann Anzahl der gewählten Objekte r (im Artikel mit k bezeichnet). ⓘ

Die Berechnung nPr (engl. Permutations) berücksichtigt die Permutationen der r Elemente, die Division durch $r!$ unterbleibt:

$P(n,r)={\frac {n!}{(n-r)!}}$. ⓘ

Berechnung des Wertes von Binomialkoeffizienten

Es gibt mehrere Methoden zur Berechnung des Wertes von ${\tbinom {n}{k}}$ zu berechnen, ohne tatsächlich eine binomische Potenz zu expandieren oder k-Kombinationen zu zählen. ⓘ

Rekursive Formel

Eine Methode verwendet die rekursive, rein additive Formel

$${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}$$

für alle ganzen Zahlen $n,k$ so dass $1\leq k\leq n-1,$ ⓘ

mit Anfangs-/Grenzwerten

$${\binom {n}{0}}={\binom {n}{n}}=1$$

für alle ganzen Zahlen $n\geq 0.$ ⓘ

Die Formel folgt aus der Betrachtung der Menge {1, 2, 3, ..., n} und der getrennten Zählung (a) der k-Element-Gruppierungen, die ein bestimmtes Mengenelement, sagen wir "i", in jeder Gruppe enthalten (da "i" bereits gewählt ist, um einen Platz in jeder Gruppe zu füllen, müssen wir nur k - 1 aus den verbleibenden n - 1 wählen) und (b) aller k-Gruppierungen, die "i" nicht enthalten; dies zählt alle möglichen k-Kombinationen von n Elementen auf. Dies ergibt sich auch aus der Verfolgung der Beiträge zu Xk in (1 + X)n-1(1 + X). Da es in (1 + X)n weder Xⁿ⁺¹ noch X-1 gibt, könnte man die Definition über die oben genannten Grenzen hinaus erweitern, um ${\tbinom {n}{k}}=0$ Diese rekursive Formel ermöglicht dann die Konstruktion des Pascalschen Dreiecks, das von Leerstellen umgeben ist, in denen sich die Nullen oder die Trivialkoeffizienten befinden würden. ⓘ

Multiplikative Formel

Eine effizientere Methode zur Berechnung der einzelnen Binomialkoeffizienten ergibt sich aus der Formel

$${\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},$$

wobei der Zähler des ersten Bruches $n^{\underline {k}}$ als fallende faktorielle Potenz ausgedrückt wird. Diese Formel ist für die kombinatorische Interpretation von Binomialkoeffizienten am einfachsten zu verstehen. Der Zähler gibt die Anzahl der Möglichkeiten an, eine Folge von k verschiedenen Objekten unter Beibehaltung der Reihenfolge der Auswahl aus einer Menge von n Objekten auszuwählen. Im Nenner steht die Anzahl der unterschiedlichen Sequenzen, die dieselbe k-Kombination bilden, wenn die Reihenfolge nicht beachtet wird. ⓘ

Aufgrund der Symmetrie des Binomialkoeffizienten in Bezug auf k und n - k kann die Berechnung optimiert werden, indem die obere Grenze des obigen Produkts auf den kleineren Wert von k und n - k festgelegt wird. ⓘ

Faktorielle Formel

Schließlich gibt es noch die kompakte, aber rechnerisch ungeeignete Form, die häufig in Beweisen und Ableitungen verwendet wird und bei der die bekannte Fakultät wiederholt zum Einsatz kommt:

$${\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,$$

wobei n! die Fakultät von n bezeichnet. Diese Formel folgt aus der obigen multiplikativen Formel, indem Zähler und Nenner mit (n - k)! multipliziert werden; folglich enthält sie viele Faktoren, die Zähler und Nenner gemeinsam haben. Für eine explizite Berechnung ist sie weniger geeignet (wenn k klein und n groß ist), es sei denn, man hebt die gemeinsamen Faktoren vorher auf (vor allem, weil die Faktorenwerte sehr schnell wachsen). Die Formel weist eine Symmetrie auf, die bei der multiplikativen Formel weniger offensichtlich ist (obwohl sie sich aus den Definitionen ergibt) ⓘ

${\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,$

(1) ⓘ

was zu einer effizienteren multiplikativen Berechnungsroutine führt. Verwendung der fallenden Fakultätsschreibweise,

$${\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}.$$

ⓘ

Verallgemeinerung und Verbindung zur binomischen Reihe

Mit der multiplikativen Formel kann die Definition der Binomialkoeffizienten erweitert werden, indem n durch eine beliebige Zahl α (negativ, reell, komplex) oder sogar ein Element eines beliebigen kommutativen Rings, in dem alle positiven ganzen Zahlen invertierbar sind, ersetzt wird:

$${\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .$$

ⓘ

Mit dieser Definition hat man eine Verallgemeinerung der Binomialformel (mit einer der Variablen auf 1 gesetzt), die es rechtfertigt, die ${\tbinom {\alpha }{k}}$ Binomialkoeffizienten zu nennen:

$(1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.$

(2) ⓘ

Diese Formel gilt für alle komplexen Zahlen α und X mit |X| < 1. Sie kann auch als Identität von formalen Potenzreihen in X interpretiert werden, wobei sie tatsächlich als Definition beliebiger Potenzen von Potenzreihen mit konstantem Koeffizienten gleich 1 dienen kann; der Punkt ist, dass mit dieser Definition alle Identitäten gelten, die man für die Potenzierung erwartet, insbesondere

$$(1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.$$

ⓘ

Wenn α eine nichtnegative ganze Zahl n ist, dann sind alle Terme mit k > n Null, und die unendliche Reihe wird zu einer endlichen Summe, wodurch die Binomialformel wiederhergestellt wird. Für andere Werte von α, einschließlich negativer ganzer Zahlen und rationaler Zahlen, ist die Reihe jedoch wirklich unendlich. ⓘ

Pascalsches Dreieck

1000. Zeile des Pascalschen Dreiecks, vertikal angeordnet, mit Graustufendarstellungen der Dezimalziffern der Koeffizienten, rechtsbündig. Der linke Rand des Bildes entspricht in etwa dem Graphen des Logarithmus der Binomialkoeffizienten und verdeutlicht, dass sie eine logarithmisch konkave Folge bilden. ⓘ

Die Pascalsche Regel ist die wichtige Rekursionsrelation

${n \choose k}+{n \choose k+1}={n+1 \choose k+1},$

(3)

mit der man durch mathematische Induktion beweisen kann, dass ${\tbinom {n}{k}}$ eine natürliche Zahl für alle ganzen Zahlen n ≥ 0 und alle ganzen Zahlen k ist, eine Tatsache, die aus Formel (1) nicht unmittelbar ersichtlich ist. Links und rechts des Pascalschen Dreiecks sind die Einträge (als Leerzeichen dargestellt) alle Null. ⓘ

Aus der Pascalschen Regel ergibt sich auch das Pascalsche Dreieck:

0:									1								ⓘ
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

Die Zeile n enthält die Zahlen ${\tbinom {n}{k}}$ für k = 0, ..., n. Es wird konstruiert, indem zuerst 1en in die äußersten Positionen gesetzt werden und dann jede innere Position mit der Summe der beiden Zahlen direkt darüber gefüllt wird. Diese Methode ermöglicht die schnelle Berechnung von Binomialkoeffizienten, ohne dass Brüche oder Multiplikationen erforderlich sind. Betrachtet man zum Beispiel die Zeile Nummer 5 des Dreiecks, so kann man schnell ablesen, dass

$(x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.$ ⓘ

Kombinatorik und Statistik

Binomialkoeffizienten sind in der Kombinatorik von Bedeutung, da sie fertige Formeln für bestimmte häufige Zählprobleme liefern:

• Es gibt ${\tbinom {n}{k}}$ Möglichkeiten, k Elemente aus einer Menge von n Elementen auszuwählen. Siehe Kombination.
• Es gibt ${\tbinom {n+k-1}{k}}$ Wege, um k Elemente aus einer Menge von n Elementen auszuwählen, wenn Wiederholungen erlaubt sind. Siehe Multiset.
• Es gibt ${\tbinom {n+k}{k}}$ Zeichenketten, die k Einsen und n Nullen enthalten.
• Es gibt ${\tbinom {n+1}{k}}$ Zeichenketten, die aus k Einsen und n Nullen bestehen, so dass keine zwei Einsen nebeneinander liegen.
• Die katalanischen Zahlen sind ${\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$
• Die Binomialverteilung in der Statistik ist ${\tbinom {n}{k}}p^{k}(1-p)^{n-k}.$ ⓘ

Binomialkoeffizienten als Polynome

Für jede nichtnegative ganze Zahl k kann der Ausdruck ${\textstyle {\binom {t}{k}}}$ vereinfacht werden und als Polynom geteilt durch k! definiert werden:

${\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};$ ⓘ

Dies stellt ein Polynom in t mit rationalen Koeffizienten dar. ⓘ

Als solches kann es bei jeder reellen oder komplexen Zahl t ausgewertet werden, um Binomialkoeffizienten mit solchen ersten Argumenten zu definieren. Diese "verallgemeinerten Binomialkoeffizienten" erscheinen in Newtons verallgemeinertem Binomialsatz. ⓘ

Für jedes k kann das Polynom ${\tbinom {t}{k}}$ als das einzige Polynom p(t) vom Grad k charakterisiert werden, das p(0) = p(1) = ⋯ = p(k - 1) = 0 und p(k) = 1 erfüllt. ⓘ

Seine Koeffizienten sind durch Stirlingzahlen erster Art ausdrückbar:

${\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.$

Die Ableitung von ${\tbinom {t}{k}}$ kann durch logarithmische Differenzierung berechnet werden:

${\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.$

Dies kann zu einem Problem führen, wenn die Ableitung bei ganzen Zahlen von $0$ bis $t-1$ausgewertet werden, aber mit Hilfe der nachstehenden Identitäten können wir die Ableitung berechnen als:

${\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.$ ⓘ

Binomialkoeffizienten als Basis für den Raum der Polynome

Über jedem Feld der Charakteristik 0 (d.h. jedem Feld, das die rationalen Zahlen enthält) ist jedes Polynom p(t) von höchstens d Grad eindeutig als Linearkombination ${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$ von Binomialkoeffizienten. Der Koeffizient ak ist die k-te Differenz der Folge p(0), p(1), ..., p(k). Explizit,

$a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).$

(4) ⓘ

Ganzzahlige Polynome

Jedes Polynom ${\tbinom {t}{k}}$ ist ganzzahlig: Es hat einen ganzzahligen Wert bei allen ganzzahligen Eingaben $t$. (Eine Möglichkeit, dies zu beweisen, ist die Induktion auf k unter Verwendung der Pascalschen Identität.) Daher ist auch jede ganzzahlige Linearkombination von Polynomen mit binomischen Koeffizienten ganzzahlig. Umgekehrt zeigt (4), dass jedes ganzzahlige Polynom eine ganzzahlige Linearkombination dieser Polynome mit Binomialkoeffizienten ist. Allgemeiner ausgedrückt: Für jeden Unterring R eines Feldes K der Charakteristik 0 nimmt ein Polynom in K[t] Werte in R zu allen ganzen Zahlen an, wenn und nur wenn es eine R-Linearkombination von Polynomen mit binomischen Koeffizienten ist. ⓘ

Beispiel

Das ganzzahlige Polynom 3t(3t + 1) / 2 kann umgeschrieben werden als

$9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.$ ⓘ

Identitäten mit Binomialkoeffizienten

Die faktorielle Formel erleichtert es, nahe beieinander liegende Binomialkoeffizienten in Beziehung zu setzen. Wenn zum Beispiel k eine positive ganze Zahl ist und n beliebig ist, dann

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}$

(5) ⓘ

und mit ein wenig mehr Arbeit

${\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.$ ⓘ

Wir können auch erhalten

${\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.$ ⓘ

Darüber hinaus kann das Folgende nützlich sein:

${\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}={\binom {n}{h+k}}{\binom {h+k}{h}}.$ ⓘ

Für konstantes n haben wir die folgende Rekursion:

${\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.$ ⓘ

Zusammenfassend haben wir

${\binom {n}{k}}={\binom {n}{n-k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}={\frac {n}{n-k}}{\binom {n-1}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.$ ⓘ

Summen der Binomialkoeffizienten

Die Formel

$\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}$

(∗∗)

besagt, dass die Elemente in der n-ten Zeile des Pascalschen Dreiecks immer die Summe 2 hoch n ergeben. Dies ergibt sich aus dem Binomischen Lehrsatz (∗), indem man x = 1 und y = 1 setzt. Die Formel hat auch eine natürliche kombinatorische Interpretation: Die linke Seite summiert die Anzahl der Teilmengen von {1, ..., n} der Größe k = 0, 1, ..., n und ergibt die Gesamtzahl der Teilmengen. (Das heißt, die linke Seite zählt die Potenzmenge von {1, ..., n}.) Diese Teilmengen können jedoch auch durch sukzessives Auswählen oder Ausschließen jedes Elements 1, ..., n erzeugt werden; die n unabhängigen binären Auswahlmöglichkeiten (Bit-Strings) erlauben eine Gesamtzahl von $2^{n}$ Auswahlmöglichkeiten. Die linke und die rechte Seite sind zwei Möglichkeiten, die gleiche Sammlung von Teilmengen zu zählen, sie sind also gleich. ⓘ

Die Formeln

$\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}$

(6)

und

$\sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}$

ergeben sich aus dem Binomischen Lehrsatz, wenn man nach x differenziert (zweimal für letzteres) und dann x = y = 1 einsetzt. ⓘ

Die Chu-Vandermonde-Identität, die für alle komplexen Werte m und n und jede nichtnegative ganze Zahl k gilt, lautet

$\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}$

(7)

und lässt sich durch Untersuchung des Koeffizienten von $x^{k}$ in der Erweiterung von (1 + x)^m(1 + x)n-m = (1 + x)n unter Verwendung von Gleichung (2). Wenn m = 1 ist, reduziert sich Gleichung (7) auf Gleichung (3). Für den Sonderfall n = 2m, k = m wird die Erweiterung (7) unter Verwendung von (1) zu (wie im Pascalschen Dreieck rechts zu sehen)

${\begin{array}{c}1\\1\qquad 1\\1\qquad 2\qquad 1\\{\color {blue}1\qquad 3\qquad 3\qquad 1}\\1\qquad 4\qquad 6\qquad 4\qquad 1\\1\qquad 5\qquad 10\qquad 10\qquad 5\qquad 1\\1\qquad 6\qquad 15\qquad {\color {red}20}\qquad 15\qquad 6\qquad 1\\1\qquad 7\qquad 21\qquad 35\qquad 35\qquad 21\qquad 7\qquad 1\end{array}}$

Pascalsches Dreieck, Zeilen 0 bis 7. Gleichung 8 für m = 3 wird in den Zeilen 3 und 6 wie folgt dargestellt $1^{2}+3^{2}+3^{2}+1^{2}=20.$

$\sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},$

(8)

wobei der Term auf der rechten Seite ein zentraler Binomialkoeffizient ist. ⓘ

Eine andere Form der Chu-Vandermonde-Identität, die für beliebige ganze Zahlen j, k und n gilt, die 0 ≤ j ≤ k ≤ n erfüllen, lautet

$\sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.$

(9)

Der Beweis ist ähnlich, verwendet aber die binomische Reihenentwicklung (2) mit negativen ganzzahligen Exponenten. Wenn j = k ist, ergibt Gleichung (9) die Hockey-Stick-Identität

$\sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}$

und deren Relation

$\sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.$ ⓘ

F(n) bezeichne die n-te Fibonacci-Zahl. Dann ist

$\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).$

Dies kann durch Induktion mit (3) oder durch die Zeckendorfsche Darstellung bewiesen werden. Ein kombinatorischer Beweis wird weiter unten gegeben. ⓘ

Multisektionen von Summen

Für solche ganzen Zahlen s und t, dass $0\leq t<s,$ ergibt die Serienmultisektion die folgende Identität für die Summe der Binomialkoeffizienten:

${\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{s}}\sum _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}.$ ⓘ

Für kleine s haben diese Reihen besonders schöne Formen, zum Beispiel, ⓘ

${\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)$

${\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)$

${\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)$

${\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)$

${\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)$

${\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)$

${\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)$ ⓘ

Partielle Summen

Es gibt zwar keine geschlossene Formel für Partialsummen ⓘ

$\sum _{j=0}^{k}{\binom {n}{j}}$ ⓘ

von Binomialkoeffizienten gibt, kann man wiederum mit (3) und Induktion zeigen, dass für k = 0, ..., n - 1,

$\sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},$ ⓘ

mit dem Sonderfall ⓘ

$\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0$ ⓘ

für n > 0. Das letztgenannte Ergebnis ist auch ein Spezialfall des Ergebnisses aus der Theorie der endlichen Differenzen, dass für jedes Polynom P(x) vom Grad kleiner als n,

$\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.$

Wenn man (2) k-mal differenziert und x = -1 setzt, ergibt sich dies für $P(x)=x(x-1)\cdots (x-k+1)$, wenn 0 ≤ k < n, und der allgemeine Fall folgt, indem man Linearkombinationen von diesen nimmt. ⓘ

Wenn P(x) vom Grad kleiner als oder gleich n ist,

$\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}$

(10)

wobei $a_{n}$ der Koeffizient vom Grad n in P(x) ist. ⓘ

Allgemeiner für (10),

$\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}$

wobei m und d komplexe Zahlen sind. Dies folgt unmittelbar aus der Anwendung von (10) auf das Polynom $Q(x):=P(m+dx)$ anstelle von $P(x)$anwendet, und feststellt, dass $Q(x)$ immer noch einen Grad kleiner oder gleich n hat und dass sein Koeffizient vom Grad n dnan ist. ⓘ

Die Reihe ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$ ist konvergent für k ≥ 2. Diese Formel wird bei der Analyse des deutschen Panzerproblems verwendet. Sie folgt aus ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{M}{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}-{\frac {1}{\binom {M+x}{k-1}}}}$ die durch Induktion auf M bewiesen wird. ⓘ

Identitäten mit kombinatorischen Beweisen

Viele Identitäten, die Binomialkoeffizienten beinhalten, können mit kombinatorischen Mitteln bewiesen werden. Zum Beispiel kann für nichtnegative ganze Zahlen ${n}\geq {q}$die Identität ⓘ

$\sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}$ ⓘ

(die sich auf (6) reduziert, wenn q = 1) wie folgt durch Doppelzählung bewiesen werden. Die linke Seite zählt die Anzahl der Möglichkeiten, eine Teilmenge von [n] = {1, 2, ..., n} mit mindestens q Elementen auszuwählen und q Elemente unter den ausgewählten zu markieren. Die rechte Seite zählt dasselbe, denn es gibt ${\tbinom {n}{q}}$ Möglichkeiten, eine Menge von q zu markierenden Elementen auszuwählen, und $2^{n-q}$ zu wählen, welche der verbleibenden Elemente von [n] ebenfalls zu dieser Teilmenge gehören. ⓘ

In der Pascalschen Identität

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k},$

zählen beide Seiten die Anzahl der k-elementigen Teilmengen von [n]: Die beiden Terme auf der rechten Seite gruppieren sie in solche, die das Element n enthalten, und solche, die es nicht enthalten. ⓘ

Die Identität (8) hat auch einen kombinatorischen Beweis. Die Identität lautet ⓘ

$\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.$ ⓘ

Angenommen, Sie haben $2n$ leere Quadrate, die in einer Reihe angeordnet sind, und man möchte n von ihnen markieren (auswählen). Es gibt ${\tbinom {2n}{n}}$ Möglichkeiten, dies zu tun. Andererseits können Sie Ihre n Quadrate auswählen, indem Sie k Quadrate aus den ersten n und $n-k$ Quadrate aus den verbleibenden n Quadraten auswählt; jedes k von 0 bis n ist möglich. Dies ergibt

$\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.$

Wenden Sie nun (1) an, um das Ergebnis zu erhalten. ⓘ

Wenn man mit F(i) die Folge der Fibonacci-Zahlen bezeichnet, die so indiziert sind, dass F(0) = F(1) = 1 ist, dann hat die Identität

$$\sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)$$

den folgenden kombinatorischen Beweis. Man kann durch Induktion zeigen, dass F(n) die Anzahl der Möglichkeiten zählt, wie ein n × 1 Streifen von Quadraten durch 2 × 1 und 1 × 1 Kacheln bedeckt werden kann. Wenn ein solcher Streifen genau k der 2 × 1-Kacheln verwendet, dann verwendet er n - 2k der 1 × 1-Kacheln, also insgesamt n - k Kacheln. Es gibt ${\tbinom {n-k}{k}}$ Möglichkeiten, diese Kacheln zu ordnen, und so ergibt die Summierung dieses Koeffizienten über alle möglichen Werte von k die Identität. ⓘ

Summe der Koeffizientenreihe

Die Anzahl der k-Kombinationen für alle k, ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ist die Summe der n-ten Zeile (von 0 an gezählt) der Binomialkoeffizienten. Diese Kombinationen werden durch die 1-Stellen der Menge der Basis-2-Zahlen von 0 bis ... aufgezählt. $2^{n}-1$wobei jede Ziffernposition eine Position aus der Menge von n ist. ⓘ

Dixonsche Identität

Die Dixon-Identität ist ⓘ

$\sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}$ ⓘ

oder, allgemeiner ausgedrückt, ⓘ

$\sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,$ ⓘ

wobei a, b und c nichtnegative ganze Zahlen sind. ⓘ

Kontinuierliche Identitäten

Bestimmte trigonometrische Integrale haben Werte, die durch Binomialkoeffizienten ausgedrückt werden können: Für jede $m,n\in \mathbb {N} ,$ ⓘ

$\int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}$

$\int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n+1)/2}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ odd}}\\0,&{\text{otherwise}}\end{cases}}$

$\int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n/2)}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ even}}\\0,&{\text{otherwise}}\end{cases}}$ ⓘ

Diese können bewiesen werden, indem man die Eulersche Formel verwendet, um trigonometrische Funktionen in komplexe Exponentiale umzuwandeln, mit Hilfe des Binomischen Satzes expandiert und Term für Term integriert. ⓘ

Kongruenzen

Wenn n eine Primzahl ist, dann

$${\binom {n-1}{k}}\equiv (-1)^{k}\mod n$$

für jedes k mit $0\leq k\leq n-1.$ Allgemeiner ausgedrückt gilt dies, wenn n eine beliebige Zahl ist und k so beschaffen ist, dass alle Zahlen zwischen 1 und k zu n koprim sind. ⓘ

In der Tat, wir haben

${\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.$ ⓘ

Generierende Funktionen

Gewöhnliche erzeugende Funktionen

Für ein festes n ist die gewöhnliche Erzeugungsfunktion der Folge ${\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots$ die Funktion

$\sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.$ ⓘ

Für ein festes k ist die gewöhnliche Erzeugungsfunktion der Folge ${\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots ,$ die Funktion

$\sum _{n=0}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.$ ⓘ

Die bivariate Erzeugungsfunktion der Binomialkoeffizienten ist

$\sum _{n=0}^{\infty }\sum _{k=0}^{n}{n \choose k}x^{k}y^{n}={\frac {1}{1-y-xy}}.$ ⓘ

Eine symmetrische bivariate Erzeugungsfunktion der Binomialkoeffizienten ist

$\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}x^{k}y^{n}={\frac {1}{1-x-y}}.$ ⓘ

Sie ist die gleiche wie die vorherige Erzeugungsfunktion nach der Substitution $x\to xy$. ⓘ

Exponentiale Erzeugungsfunktion

Eine symmetrische exponentielle bivariate Erzeugungsfunktion der Binomialkoeffizienten ist:

$\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.$ ⓘ

Teilbarkeitseigenschaften

1852 bewies Kummer, dass, wenn m und n nichtnegative ganze Zahlen sind und p eine Primzahl ist, die größte Potenz von p, die ${\tbinom {m+n}{m}}$ glei^ch pc ist, wobei c die Anzahl der Überträge ist, wenn m und n zur Basis p addiert werden. Äquivalent dazu ist der Exponent einer Primzahl p in ${\tbinom {n}{k}}$ ist gleich der Anzahl der nichtnegativen ganzen Zahlen j, so dass der Bruchteil von k/p^j größer ist als der Bruchteil von n/p^j. Daraus lässt sich ableiten, dass ${\tbinom {n}{k}}$ durch n/gcd(n,k) teilbar ist. Insbesondere folgt daraus, dass p teilbar ist durch ${\tbinom {p^{r}}{s}}$ für alle positiven ganzen Zahlen r und s, so dass s < pr ist. Dies gilt jedoch nicht für höhere Potenzen von p: 9 ist zum Beispiel nicht teilbar. ${\tbinom {9}{6}}$. ⓘ

Ein etwas überraschendes Ergebnis von David Singmaster (1974) ist, dass jede ganze Zahl fast alle Binomialkoeffizienten teilt. Genauer gesagt, man setze eine ganze Zahl d fest und lasse f(N) die Anzahl der binomischen Koeffizienten bezeichnen ${\tbinom {n}{k}}$ mit n < N, so dass d dividiert ${\tbinom {n}{k}}$. Dann

$\lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.$

Da die Anzahl der Binomialkoeffizienten ${\tbinom {n}{k}}$ mit n < N gleich N(N + 1) / 2 ist, bedeutet dies, dass die Dichte der Binomialkoeffizienten, die durch d teilbar sind, gegen 1 geht. ⓘ

Binomialkoeffizienten haben Teilbarkeitseigenschaften, die sich auf die kleinsten gemeinsamen Vielfachen von aufeinanderfolgenden ganzen Zahlen beziehen. Zum Beispiel: ${\binom {n+k}{k}}$ dividiert ${\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n}}$. ⓘ

${\binom {n+k}{k}}$ ist ein Vielfaches von ${\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n\cdot \operatorname {lcm} ({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}$. ⓘ

Eine weitere Tatsache: Eine ganze Zahl n ≥ 2 ist dann und nur dann prim, wenn alle binomischen Zwischenkoeffizienten

${\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}$

durch n teilbar sind. ⓘ

Beweis: Wenn p eine Primzahl ist, ist p teilbar durch

${\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}$ für alle 0 < k < p

weil ${\tbinom {p}{k}}$ eine natürliche Zahl ist und p zwar den Zähler, nicht aber den Nenner teilt. Wenn n zusammengesetzt ist, sei p der kleinste Primfaktor von n und k = n/p. Dann ist 0 < p < n und

${\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}\not \equiv 0{\pmod {n}}$

sonst muss der Zähler k(n - 1)(n - 2)⋯(n - p + 1) durch n = k×p teilbar sein, was nur dann der Fall sein kann, wenn (n - 1)(n - 2)⋯(n - p + 1) durch p teilbar ist. Da aber n durch p teilbar ist, teilt p nicht n - 1, n - 2, ..., n - p + 1, und da p eine Primzahl ist, wissen wir, dass p nicht (n - 1)(n - 2)⋯(n - p + 1) teilt und somit der Zähler nicht durch n teilbar ist. ⓘ

Schranken und asymptotische Formeln

Die folgenden Schranken für ${\tbinom {n}{k}}$ gelten für alle Werte von n und k, so dass 1 ≤ k ≤ n:

$${\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.$$

Die erste Ungleichung folgt aus der Tatsache, dass

$${n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}$$

und jeder dieser $k$ Terme in diesem Produkt sind ${\textstyle \geq {\frac {n}{k}}}$. Mit einer ähnlichen Argumentation lässt sich die zweite Ungleichung zeigen. Die letzte strenge Ungleichung ist äquivalent zu ${\textstyle e^{k}>k^{k}/k!}$Das ist klar, denn die rechte Seite ist ein Term der Exponentialreihe ${\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$. ⓘ

Aus den Teilbarkeitseigenschaften können wir ableiten, dass

$${\frac {\operatorname {lcm} (n-k,\ldots ,n)}{(n-k)\cdot \operatorname {lcm} \left({\binom {k}{0}},\ldots ,{\binom {k}{k}}\right)}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{n-k}},$$

wobei beide Ungleichungen erreicht werden können. ⓘ

Die folgenden Schranken sind in der Informationstheorie nützlich:

$${\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}$$

wobei $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ ist die binäre Entropiefunktion. Sie kann weiter verschärft werden zu

$${\sqrt {\frac {n}{8k(n-k)}}}2^{nH(k/n)}\leq {n \choose k}\leq {\sqrt {\frac {n}{\pi k(n-k)}}}2^{nH(k/n)}$$

für alle $1\leq k\leq n-1$. ⓘ

Sowohl n als auch k groß

Die Stirlingsche Näherung führt zu folgender Näherung, die gilt, wenn $n,k$ beide gegen unendlich tendieren:

$${n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}$$

Da die Ungleichungsformen der Stirling-Formel auch die Faktoren begrenzen, ergeben leichte Varianten der obigen asymptotischen Approximation exakte Schranken. Insbesondere, wenn $n$ hinreichend groß ist, erhält man

$${2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}$$

und ${\sqrt {n}}{2n \choose n}\geq 2^{2n-1}$ und, allgemeiner, für m ≥ 2 und n ≥ 1,

$${\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.$$

ⓘ

Wenn n groß ist und k linear in n ist, gibt es verschiedene genaue asymptotische Schätzungen für den Binomialkoeffizienten ${\textstyle {\binom {n}{k}}}$. Zum Beispiel, wenn $|n/2-k|=o(n^{2/3})$ dann

$${\binom {n}{k}}\sim {\binom {n}{\frac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}$$

mit d = n - 2k. ⓘ

n viel größer als k

Wenn n groß ist und k o(n) ist (d. h. wenn k/n → 0), dann

$${\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)$$

wobei o wiederum die kleine o-Schreibweise ist. ⓘ

Summen der Binomialkoeffizienten

Eine einfache und grobe obere Schranke für die Summe der Binomialkoeffizienten lässt sich mit Hilfe des Binomischen Lehrsatzes ermitteln:

$$\sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}$$

Genauere Schranken sind gegeben durch

$${\frac {1}{\sqrt {8n\varepsilon (1-\varepsilon )}}}\cdot 2^{H(\varepsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\varepsilon )\cdot n},$$

gültig für alle ganzen Zahlen $n>k\geq 1$ mit $\varepsilon \doteq k/n\leq 1/2$. ⓘ

Verallgemeinerte Binomialkoeffizienten

Die unendliche Produktformel für die Gamma-Funktion liefert auch einen Ausdruck für Binomialkoeffizienten

$$(-1)^{k}{z \choose k}={-z+k-1 \choose k}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}$$

die zu den asymptotischen Formeln führen

$${z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{and}}\qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)$$

als $k\to \infty$. ⓘ

Dieses asymptotische Verhalten ist in der Approximation

$${z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}$$

ebenfalls enthalten. (Hier $H_{k}$ ist die k-te harmonische Zahl und $\gamma$ ist die Euler-Mascheroni-Konstante.) ⓘ

Außerdem gilt die asymptotische Formel

$${\frac {z+k \choose j}{k \choose j}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {j \choose j-k}{j-z \choose j-k}}\to \left({\frac {j}{k}}\right)^{z}$$

gilt immer dann, wenn $k\to \infty$ und $j/k\to x$ für eine komplexe Zahl $x$. ⓘ

Verallgemeinerungen

Verallgemeinerung auf Multinomiale

Binomialkoeffizienten können zu Multinomialkoeffizienten verallgemeinert werden, die als Zahl definiert sind:

${n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}$

wobei

$\sum _{i=1}^{r}k_{i}=n.$ ⓘ

Während die Binomialkoeffizienten die Koeffizienten von (x+y)n darstellen, stellen die Multinomialkoeffizienten für die Koeffizienten des Polynoms

$(x_{1}+x_{2}+\cdots +x_{r})^{n}.$

Der Fall r = 2 ergibt Binomialkoeffizienten:

${n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.$ ⓘ

Die kombinatorische Interpretation der Multinomialkoeffizienten ist die Verteilung von n unterscheidbaren Elementen über r (unterscheidbare) Behälter, die jeweils genau ki Elemente enthalten, wobei i der Index des Behälters ist. ⓘ

Mult_inomialkoeffizienten haben viele ähnliche Eigenschaften wie Binomialkoeffizienten, zum Beispiel die Rekursionsrelation:

${n \choose k_{1},k_{2},\ldots ,k_{r}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}$

und Symmetrie:

${n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}$

wobei $(\sigma _{i})$ ist eine Permutation von (1, 2, ..., r). ⓘ

Taylor-Reihen

Unter Verwendung von Stirlingzahlen erster Art ist die Reihenentwicklung um einen beliebig gewählten Punkt $z_{0}$ die Funktion

${\begin{aligned}{z \choose k}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{z_{0} \choose j-i}{\frac {s_{k+i-j,i}}{(k+i-j)!}}\\&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}z_{0}^{j-i}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}$ ⓘ

Binomialkoeffizient mit n = 1/2

Die Definition der Binomialkoeffizienten kann auf den Fall erweitert werden, dass $n$ reell ist und $k$ eine ganze Zahl ist. ⓘ

Insbesondere gilt die folgende Identität für jede nichtnegative ganze Zahl $k$:

${{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.$ ⓘ

Dies zeigt sich bei der Erweiterung ${\sqrt {1+x}}$ in eine Potenzreihe unter Verwendung der Newtonschen Binomialreihe:

${\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.$ ⓘ

Produkte von Binomialkoeffizienten

Man kann das Produkt zweier Binomialkoeffizienten als Linearkombination von Binomialkoeffizienten ausdrücken:

${z \choose m}{z \choose n}=\sum _{k=0}^{m}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},$ ⓘ

wobei die Verbindungskoeffizienten Multinomialkoeffizienten sind. In Bezug auf etikettierte kombinatorische Objekte stellen die Verbindungskoeffizienten die Anzahl der Möglichkeiten dar, einem Paar etikettierter kombinatorischer Objekte mit dem Gewicht m bzw. n, deren erste k Etiketten identifiziert wurden, m + n - k Etiketten zuzuordnen oder sie zusammenzukleben, um ein neues etikettiertes kombinatorisches Objekt mit dem Gewicht m + n - k zu erhalten (d. h. die Etiketten in drei Teile aufzuteilen, die auf den geklebten Teil, den ungeklebten Teil des ersten Objekts und den ungeklebten Teil des zweiten Objekts anzuwenden sind). In dieser Hinsicht sind Binomialkoeffizienten für exponentielle Erzeugungsreihen das, was fallende Faktorielle für gewöhnliche Erzeugungsreihen sind. ⓘ

Das Produkt aller Binomialkoeffizienten in der n-ten Zeile des Pascalschen Dreiecks ist durch die Formel gegeben:

$\prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.$ ⓘ

Partielle Bruchzerlegung

Die partielle Bruchzerlegung des Kehrwerts ist gegeben durch

${\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.$ ⓘ

Newtonsche Binomische Reihe

Die Newtonsche Binomische Reihe, benannt nach Sir Isaac Newton, ist eine Verallgemeinerung des Binomischen Satzes auf unendliche Reihen:

$(1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .$ ⓘ

Die Identität kann erhalten werden, indem man zeigt, dass beide Seiten die Differentialgleichung (1 + z) f(z) = α f(z) erfüllen. ⓘ

Der Konvergenzradius dieser Reihe ist 1. Ein alternativer Ausdruck ist ⓘ

${\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}$ ⓘ

wobei die Identität ⓘ

${n \choose k}=(-1)^{k}{k-n-1 \choose k}$ ⓘ

angewendet wird. ⓘ

Multiset (steigender) Binomialkoeffizient

Binomialkoeffizienten zählen Teilmengen vorgegebener Größe aus einer gegebenen Menge. Ein verwandtes kombinatorisches Problem ist die Zählung von Multisets vorgegebener Größe mit Elementen aus einer gegebenen Menge, d. h. die Zählung der Möglichkeiten, eine bestimmte Anzahl von Elementen aus einer gegebenen Menge auszuwählen, wobei die Möglichkeit besteht, dasselbe Element wiederholt auszuwählen. Die sich daraus ergebenden Zahlen werden Multiset-Koeffizienten genannt; die Anzahl der Möglichkeiten, k Elemente aus einer Menge mit n Elementen auszuwählen, wird mit ${\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}$. ⓘ

Um Zweideutigkeiten und Verwechslungen mit der Hauptbezeichnung von n in diesem Artikel zu vermeiden,
sei f = n = r + (k - 1) und r = f - (k - 1). ⓘ

Multiset-Koeffizienten lassen sich durch die Binomialkoeffizienten nach folgender Regel ausdrücken

$${\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.$$

Eine mögliche alternative Charakterisierung dieser Identität lautet wie folgt: Wir können die fallende Fakultät definieren als

$$(f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,$$

und die entsprechende steigende Fakultät als

$$r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);$$

so zum Beispiel,

$$17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.$$

Dann können die Binomialkoeffizienten geschrieben werden als

$${\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}},$$

geschrieben werden, während der entsprechende Multiset-Koeffizient durch Ersetzen der fallenden durch die steigende Fakultät definiert wird:

$$\left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}.$$

ⓘ

Verallgemeinerung auf negative ganze Zahlen n

Binomialkoeffizienten C (n, k) erweitert für negatives und gebrochenes n, veranschaulicht mit einem einfachen Binom. Es ist zu beobachten, dass das Pascalsche Dreieck gedreht wird und die alternativen Terme negiert werden. Der Fall n = -1 ergibt die Grandi-Reihe. ⓘ

Für jedes n, ⓘ

${\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\;.\end{aligned}}$

Insbesondere sind Binomialkoeffizienten, die bei negativen ganzen Zahlen n ausgewertet werden, durch vorzeichenbehaftete Multiset-Koeffizienten gegeben. Im Spezialfall $n=-1$reduziert sich dies auf $(-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).$ ⓘ

Wenn zum Beispiel n = -4 und k = 7, dann ist r = 4 und f = 10:

${\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}$ ⓘ

Zwei reelle oder komplexwertige Argumente

Der Binomialkoeffizient wird auf zwei reelle oder komplexwertige Argumente verallgemeinert, indem man die Gammafunktion oder die Betafunktion über

${x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (y+1,x-y+1)}}.$

Diese Definition erbt die folgenden zusätzlichen Eigenschaften von $\Gamma$:

${x \choose y}={\frac {\sin(y\pi )}{\sin(x\pi )}}{-y-1 \choose -x-1}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{y-x-1 \choose y};$

geerbt,

${x \choose y}\cdot {y \choose x}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.$ ⓘ

Die sich daraus ergebende Funktion ist wenig erforscht und wurde offenbar erstmals in (Fowler 1996) grafisch dargestellt. Insbesondere versagen viele binomische Identitäten: ${\textstyle {\binom {n}{m}}={\binom {n}{n-m}}}$ aber ${\textstyle {\binom {-n}{m}}\neq {\binom {-n}{-n-m}}}$ für n positiv (also $-n$ negativ). Das Verhalten ist recht komplex und unterscheidet sich deutlich in verschiedenen Oktanten (d. h. in Bezug auf die x- und y-Achsen und die Linie $y=x$), wobei das Verhalten für negatives x Singularitäten bei negativen ganzzahligen Werten und ein Schachbrettmuster aus positiven und negativen Bereichen aufweist:

• im Oktant $0\leq y\leq x$ handelt es sich um eine glatt interpolierte Form des gewöhnlichen Binoms, mit einem Grat ("Pascalscher Grat").
• im Oktant $0\leq x\leq y$ und im Quadranten $x\geq 0,y\leq 0$ liegt die Funktion nahe bei Null.
• im Quadranten $x\leq 0,y\geq 0$ ist die Funktion abwechselnd sehr groß, positiv und negativ auf den Parallelogrammen mit Scheitelpunkten
  $$(-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)$$
• im Oktant $0>x>y$ das Verhalten ist wiederum abwechselnd sehr groß positiv und negativ, aber auf einem quadratischen Gitter.
• im Oktant $-1>y>x+1$ Sie ist nahe bei Null, außer in der Nähe der Singularitäten. ⓘ

Verallgemeinerung auf q-Reihen

Der Binomialkoeffizient hat eine q-analoge Verallgemeinerung, die als Gaußscher Binomialkoeffizient bekannt ist. ⓘ

Verallgemeinerung auf unendliche Kardinalzahlen

Die Definition des Binomialkoeffizienten kann durch Definition auf unendliche Kardinalzahlen verallgemeinert werden:

${\alpha \choose \beta }=\left|\left\{B\subseteq A:\left|B\right|=\beta \right\}\right|$ ⓘ

wobei A eine Menge mit Kardinalität ist $\alpha$. Man kann zeigen, dass der verallgemeinerte Binomialkoeffizient wohldefiniert ist, in dem Sinne, dass unabhängig von der gewählten Menge die Kardinalzahl $\alpha$, ${\textstyle {\alpha \choose \beta }}$ die gleiche bleibt. Für endliche Kardinalzahlen stimmt diese Definition mit der Standarddefinition des Binomialkoeffizienten überein. ⓘ

Unter der Annahme des Axioms der Wahl kann man zeigen, dass ${\textstyle {\alpha \choose \alpha }=2^{\alpha }}$ für jede unendliche Kardinalzahl $\alpha$. ⓘ

In Programmiersprachen

Die Schreibweise ${\textstyle {n \choose k}}$ ist praktisch für die Handschrift, aber unbequem für Schreibmaschinen und Computerterminals. Viele Programmiersprachen bieten kein Standard-Unterprogramm zur Berechnung des Binomialkoeffizienten an, aber zum Beispiel verwenden sowohl die Programmiersprache APL als auch die (verwandte) Programmiersprache J das Ausrufezeichen: k ! n. Der Binomialkoeffizient ist in SciPy als scipy.special.comb implementiert. ⓘ

Naive Implementierungen der faktoriellen Formel, wie z.B. das folgende Snippet in Python:

from math import factorial
def binomial_coefficient(n: int, k: int) -> int:
    return factorial(n) // (factorial(k) * factorial(n - k)) <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

sind sehr langsam und unbrauchbar für die Berechnung von Fakultäten von sehr hohen Zahlen (in Sprachen wie C oder Java leiden sie aus diesem Grund unter Überlauffehlern). Eine direkte Implementierung der multiplikativen Formel funktioniert gut:

def binomial_koeffizient(n: int, k: int) -> int:
    if k < 0 oder k > n:
        return 0
    wenn k == 0 oder k == n:
        return 1
    k = min(k, n - k) # Ausnutzung der Symmetrie
    c = 1
    for i in range(k):
        c = c * (n - i) / (i + 1)
    c zurückgeben

(In Python erzeugt range(k) eine Liste von 0 bis k-1.) ⓘ

Die Pascalsche Regel bietet eine rekursive Definition, die auch in Python implementiert werden kann, obwohl sie weniger effizient ist:

def binomial_coefficient(n: int, k: int) -> int:
    if k < 0 oder k > n:
        return 0
    if k > n - k: # Symmetrie ausnutzen
        k = n - k
    wenn k == 0 oder n <= 1:
        return 1
    return binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1) <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

Das oben genannte Beispiel kann auch im funktionalen Stil geschrieben werden. Das folgende Scheme-Beispiel verwendet die rekursive Definition

${n \choose k+1}={\frac {n-k}{k+1}}{n \choose k}$

Rationale Arithmetik kann leicht durch ganzzahlige Division vermieden werden

${n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)$

Die folgende Implementierung nutzt alle diese Ideen

(define (binomial n k)
;; Hilfsfunktion zur Berechnung von C(n,k) durch Vorwärtsrekursion
  (define (binomial-iter n k i prev)
    (if (>= i k)
      prev
     (binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1)))))
;; Verwendung der Symmetrieeigenschaft C(n,k)=C(n, n-k)
  (if (< k (- n k))
    (binomial-iter n k 0 1)
    (binomial-iter n (- n k) 0 1))) <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

Beim Rechnen ${\textstyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)}$ in einer Sprache mit ganzen Zahlen fester Länge, kann die Multiplikation mit $(n-k)$ einen Überlauf verursachen, selbst wenn das Ergebnis passen würde. Der Überlauf kann vermieden werden, indem man zuerst dividiert und das Ergebnis mit Hilfe des Rests festlegt:

${n \choose k+1}=\left[{\frac {\binom {n}{k}}{(k+1)}}\right](n-k)+{\left[{n \choose k}\ \mathrm {mod} \ (k+1)\right](n-k) \over (k+1)}$ ⓘ

Implementierung in der Sprache C:

#include <limits.h> <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

unsigned long binomial(unsigned long n, unsigned long k) {
  unsigned long c = 1, i; <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

  if (k > n-k) // Symmetrie ausnutzen
    k = n-k; <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

  for (i = 1; i <= k; i++, n--) {
    if (c/i >= ULONG_MAX/n) // bei möglichem Überlauf 0 zurückgeben
      0 zurückgeben; <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

    c = c / i * n + c % i * n / i; // Aufteilung von c * n / i in (c / i * i + c % i) * n / i
  } <span title="Aus: Englische Wikipedia, Abschnitt &quot;In programming languages&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages <span style="color:#dddddd">ⓘ</span>]</span>

  return c;
}

Eine andere Möglichkeit, den Binomialkoeffizienten bei großen Zahlen zu berechnen, ist die Erkenntnis, dass

${n \choose k}={\frac {n!}{k!\,(n-k)!}}={\frac {\Gamma (n+1)}{\Gamma (k+1)\,\Gamma (n-k+1)}}=\exp(\ln \Gamma (n+1)-\ln \Gamma (k+1)-\ln \Gamma (n-k+1)),$ ⓘ

wobei $\ln \Gamma (n)$ den natürlichen Logarithmus der Gammafunktion bei $n$. Es handelt sich um eine spezielle Funktion, die leicht zu berechnen ist und in einigen Programmiersprachen zum Standard gehört, z. B. log_gamma in Maxima, LogGamma in Mathematica, gammaln in MATLAB und dem SciPy-Modul von Python, lngamma in PARI/GP oder lgamma in C, R und Julia. Rundungsfehler können dazu führen, dass der zurückgegebene Wert keine ganze Zahl ist. ⓘ

Der Binomialkoeffizient in der Kombinatorik

Veranschaulichung mit Mengen

Variante 1

Zunächst zählt man alle $k$-Tupel mit paarweise verschiedenen Elementen, die sich aus der $n$-elementigen Ausgangsmenge zusammenstellen lassen. Es gibt $n$ Möglichkeiten der Wahl des ersten Tupel-Elements. Nach jeder beliebigen Wahl dieses ersten gibt es nur noch $n-1$ Wahlmöglichkeiten für das zweite Element, nach dessen Wahl nur noch $n-2$ für das dritte usw., bis hin zu $n-k+1$ Wahlmöglichkeiten für das $k$-te und letzte Tupel-Element. Die Anzahl aller so zusammengestellten $k$-Tupel ist also das Produkt $n\cdot (n-1)\cdot (n-2)\dotsm (n-k+2)\cdot (n-k+1)$ von $k$ Faktoren, das sich mit Hilfe der Fakultät auch als ${\tfrac {n!}{(n-k)!}}$ notieren lässt. Nun sind aber genau je $k!$ der gezählten $k$-Tupel Permutationen voneinander und entsprechen daher ein und derselben $k$-elementigen Teilmenge. Nach Division durch diese „Zähl-Vielfachheit“ ergibt sich also tatsächlich ${\tfrac {n!}{k!\cdot (n-k)!}}={\tbinom {n}{k}}$ als die gesuchte Teilmengenanzahl. ⓘ

Variante 2

Eine andere, symmetrischere Veranschaulichung betont nicht den Akt der Auswahl von $k$ aus $n$ Elementen, sondern den Aspekt der Zerlegung in zwei Teilmengen aus $k$ und $l:=n-k$ Elementen. Angenommen, ein $n=l+k$-elementiges Ausgangstupel bestehe aus $k$ roten und $l$ weißen irgendwie aufgereihten Elementen. Bildet man alle $(k+l)!$ Permutationen dieser Aufreihung, so sind je $k!\cdot l!$ davon farblich ununterscheidbar, denn je $k!$ Permutationen der roten Elemente untereinander ändern nichts an der Farbsequenz, ebenso wenig wie je $l!$ davon unabhängige Permutationen innerhalb der weißen. Es gibt also nur ${\tfrac {(k+l)!}{k!\cdot l!}}={\tbinom {k+l}{k}}={\tbinom {k+l}{l}}$ farblich verschiedene Sequenzen der Länge $k+l$ mit allen möglichen unterschiedlichen Belegungen durch je $k$ rote Elemente. Jede Sequenz lässt sich nun aber eineindeutig einer der $k$-elementigen Teilmengen einer $k+l$-elementigen Menge zuordnen. Dasselbe gilt wegen der Symmetrie von rot und weiß oder von $k$ und $l$ auch für die komplementären $l$-elementigen Teilmengen. Die Gesamtzahl dieser Teilmengen ist damit je ${\tbinom {k+l}{k}}={\tbinom {n}{k}}={\tbinom {n}{n-k}}={\tbinom {k+l}{l}}$. ⓘ

Beispiel

Für die Anzahl der möglichen Ziehungen oder Tippscheine beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) gilt:

${\tbinom {49}{6}}=13.983.816\approx 14\ {\text{Millionen}}$ ⓘ

Es gibt hier offensichtlich genau eine Möglichkeit, 6 Richtige zu tippen. ${\tbinom {43}{6}}$ zählt die Möglichkeiten für 0 Richtige, nämlich alle 6 Tipps aus den 43 Falschen zu wählen. Die Anzahl verschiedener Tipps mit 5 Richtigen ergibt sich zu $6\cdot 43=258$, denn es gibt 6 Möglichkeiten, nur 5 der 6 gezogenen Zahlen zu tippen (oder eine davon auszulassen), und dann jeweils $43=49-6$ Möglichkeiten, den ausgelassenen Tipp auf eine der 43 falschen Zahlen zu setzen. Allgemein ergibt sich die Anzahl der verschiedenen Tipps mit $r$ Richtigen bei 6 aus 49 mit derselben Überlegung zu ${\tbinom {6}{r}}\cdot {\tbinom {43}{6-r}}$. Bei 6, 0 und 5 Richtigen fällt kaum auf, dass die verwendeten Faktoren $1={\tbinom {6}{6}}={\tbinom {6}{0}}={\tbinom {43}{0}}$, $6={\tbinom {6}{5}}$ und $43={\tbinom {43}{1}}$ eigentlich einfache Binomialkoeffizienten sind. Die Summe aller genannten Tippzahlen ergibt die Gesamtzahl 13983816 aller möglichen Tipps – das folgt aus der unten angegebenen Vandermondeschen Identität. ⓘ

Die Wahrscheinlichkeit für 6 mit einem Tipp erzielte Richtige ist also $1/13983816$, die für 5 Richtige ist $258/13983816$. Für 0 Richtige ergeben sich mit $6096454/13983816$ schon etwa 44 %. Die allgemeine Wahrscheinlichkeit ${\tbinom {6}{r}}\cdot {\tbinom {43}{6-r}}/{\tbinom {49}{6}}$ für $r$ Richtige ist ein Spezialfall der hypergeometrischen Verteilung, die gerade drei Binomialkoeffizienten derart kombiniert. ⓘ

Weitere Beispiele siehe unter: Kombination (Kombinatorik) → Beispiele ⓘ

Kombinatorische Beweise

Die kombinatorische Deutung erlaubt auch einfache Beweise von Relationen zwischen Binomialkoeffizienten, etwa durch doppeltes Abzählen. Beispiel: Für $1\leq k\leq n$ gilt:

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$

Beweis: Es sei $X$ eine $n$-elementige Menge und $x\in X$ ein festes Element. Dann zerfallen die $k$-elementigen Teilmengen von $X$ in zwei Klassen:

• die Teilmengen, die $x$ enthalten; sie bestehen also aus $x$ zusammen mit einer $(k-1)$-elementigen Teilmenge der $(n-1)$-elementigen Menge $X\setminus \{x\}$,
• die Teilmengen, die $x$ nicht enthalten; sie sind $k$-elementige Teilmengen der $(n-1)$-elementigen Menge $X\setminus \{x\}$. ⓘ

Ausdrücke mit Binomialkoeffizienten

Summen mit alternierenden Binomialkoeffizienten

$\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}={\binom {n}{0}}-{\binom {n}{1}}+{\binom {n}{2}}\mp \dotsb +(-1)^{n}{\binom {n}{n}}=0$ für $n>0$.

Diese Formel folgt für ungerade $n$ aus der Symmetrie des Binomialkoeffizienten. Für beliebige $n$ lässt sie sich aus dem binomischen Lehrsatz herleiten, indem $x=1$ und $y=-1$ (oder $x=-1$ und $y=1$) gesetzt wird. ⓘ

Summen von Binomialkoeffizienten mit geraden bzw. ungeraden Anzahlen ausgewählter Objekte

Durch Subtraktion bzw. Addition obiger Gleichungen $\textstyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}$ und $\textstyle \sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}=0$ und anschließende Halbierung ist für $n>0$ zu erhalten: $\sum _{k=0}^{[{\frac {n}{2}}]}{\binom {n}{2k}}=2^{n-1}$ wie auch $\sum _{k=0}^{[{\frac {n-1}{2}}]}{\binom {n}{2k+1}}=2^{n-1}$; ⓘ

hierbei sind [] Gaußklammern. ⓘ

Summe verschobener Binomialkoeffizienten

Ausgehend vom Induktionsanfang $\textstyle \sum _{k=0}^{m=1}{\binom {n+k}{n}}={\binom {n}{n}}+{\binom {n+1}{n}}={\binom {n+1}{n+1}}+{\binom {n+1}{n}}={\binom {n+1+1}{n+1}}$ für beliebiges $n$, der die Rekursionsvorschrift für Binomialkoeffizienten nutzt, ist mit Induktion nach $m$ unter erneuter Nutzung der Rekursionsvorschrift leicht zu beweisen:

$\sum _{k=0}^{m}{\binom {n+k}{n}}={\binom {n}{n}}+{\binom {n+1}{n}}+\dotsb +{\binom {n+m}{n}}={\binom {n+m+1}{n+1}}$;

wegen Symmetrie der Summanden wie auch der Summe gilt ebenso:

$\sum _{k=0}^{m}{\binom {n+k}{k}}={\binom {n}{0}}+{\binom {n+1}{1}}+\dotsb +{\binom {n+m}{m}}={\binom {n+m+1}{m}}={\binom {n+m+1}{n+1}}$. ⓘ

Divisionsreste

Ist $p$ eine Primzahl, $n_{0},k_{0}\in \{0,\dotsc ,p-1\}$ und $n_{1},k_{1}\in \mathbb {N}$, dann ist

${\binom {n_{0}+pn_{1}}{k_{0}+pk_{1}}}\equiv {\binom {n_{0}}{k_{0}}}{\binom {n_{1}}{k_{1}}}{\pmod {p}}.$

Das heißt, modulo $p$ kann ${\tbinom {n}{k}}$ mit Hilfe der Darstellungen von $n$ und $k$ zur Basis $p$ effizient berechnet werden, nämlich „ziffernweise“. ⓘ

Trivia

Die wörtliche Übersetzung von „$n$ über $k$“ ins Englische „$n$ over $k$“ bezeichnet nicht den Binomialkoeffizienten ${\tbinom {n}{k}}$, sondern den Bruch ${\tfrac {n}{k}}$. Korrekt ist „$n$ choose $k$“. ⓘ