Die Anzahl der k-Kombinationen aus einer gegebenen Menge S von n Elementen wird in Texten der elementaren Kombinatorik oft mit C ( n , k ) {\displaystyle C(n,k)} bezeichnet
, oder durch eine Variante wie C k n {\displaystyle C_{k}^{n}}
, n C k {\displaystyle {}_{n}C_{k}}
, n C k {\displaystyle {}^{n}C_{k}}
, C n , k {\displaystyle C_{n,k}}
oder auch C n k {\displaystyle C_{n}^{k}}
(die letztere Form war in französischen, rumänischen, russischen, chinesischen und polnischen Texten üblich). Dieselbe Zahl kommt jedoch in vielen anderen mathematischen Zusammenhängen vor, wo sie mit ( n k ) {\displaystyle {\tbinom {n}{k}}} bezeichnet wird
(oft gelesen als „n wähle k“); insbesondere kommt sie als Koeffizient in der binomischen Formel vor, daher der Name Binomialkoeffizient. Man kann ( n k ) {\displaystyle {\tbinom {n}{k}}}
für alle natürlichen Zahlen k auf einmal durch die Beziehung ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}
aus dem ersichtlich ist, dass
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}
und weiter,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
für k > n.
Um zu sehen, dass diese Koeffizienten k-Kombinationen von S zählen, kann man zunächst eine Sammlung von n verschiedenen Variablen Xs betrachten, die durch die Elemente s von S bezeichnet sind, und das Produkt über alle Elemente von S erweitern:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
es hat 2n verschiedene Terme, die allen Teilmengen von S entsprechen, wobei jede Teilmenge das Produkt der entsprechenden Variablen Xs ergibt. Setzt man nun alle Xs gleich der unbeschrifteten Variablen X, so dass das Produkt (1 + X)n wird, so wird der Term für jede k-Kombination von S zu Xk, so dass der Koeffizient dieser Potenz im Ergebnis gleich der Anzahl solcher k-Kombinationen ist.
Binomialkoeffizienten können auf verschiedene Weise explizit berechnet werden. Um alle für die Expansionen bis (1 + X)n zu erhalten, kann man (zusätzlich zu den bereits genannten Grundfällen) die Rekursionsrelation
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) verwenden, {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
für 0 < k < n, was aus (1 + X)n = (1 + X)n – 1(1 + X) folgt; Dies führt zur Konstruktion des Pascalschen Dreiecks.
Für die Bestimmung eines einzelnen Binomialkoeffizienten ist es praktischer, die Formel
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k zu verwenden ! {\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}
.
Der Zähler gibt die Anzahl der k-Permutationen von n an, d. h., von Folgen von k verschiedenen Elementen von S, während der Nenner die Anzahl solcher k-Permutationen angibt, die dieselbe k-Kombination ergeben, wenn die Reihenfolge ignoriert wird.
Wenn k größer als n/2 ist, enthält die obige Formel Faktoren, die dem Zähler und dem Nenner gemeinsam sind, und wenn man sie aufhebt, erhält man die Beziehung
( n k ) = ( n n – k ) , {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}
für 0 ≤ k ≤ n. Dies drückt eine Symmetrie aus, die aus der binomischen Formel ersichtlich ist, und kann auch in Bezug auf k-Kombinationen verstanden werden, indem man das Komplement einer solchen Kombination nimmt, das eine (n – k)-Kombination ist.
Schließlich gibt es eine Formel, die diese Symmetrie direkt zeigt und den Vorzug hat, leicht zu merken zu sein:
( n k ) = n ! k ! ( n – k ) !
wobei n! die Fakultät von n bezeichnet. Sie ergibt sich aus der vorherigen Formel durch Multiplikation von Nenner und Zähler mit (n – k)!Die letzte Formel kann direkt verstanden werden, indem man die n! Permutationen aller Elemente von S betrachtet. Jede dieser Permutationen ergibt eine k-Kombination, indem man ihre ersten k Elemente auswählt. Es gibt viele doppelte Auswahlen: jede kombinierte Permutation der ersten k Elemente untereinander und der letzten (n – k) Elemente untereinander ergibt dieselbe Kombination; dies erklärt die Teilung in der Formel.
Aus den obigen Formeln folgen Beziehungen zwischen benachbarten Zahlen im Pascalschen Dreieck in allen drei Richtungen:
( n k ) = { ( n k – 1 ) n – k + 1 k wenn k > 0 ( n – 1 k ) n n – k wenn k < n ( n – 1 k – 1 ) n k wenn n , k > 0 {\displaystyle {\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}}
.
Zusammen mit den Grundfällen ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}
, diese erlauben die sukzessive Berechnung von jeweils allen Anzahlen von Kombinationen aus derselben Menge (einer Zeile im Pascalschen Dreieck), von k-Kombinationen von Mengen wachsender Größe und von Kombinationen mit einem Komplement der festen Größe n – k.
Beispiel für das Zählen von KombinationenEdit
Als konkretes Beispiel kann man die Anzahl der möglichen Fünf-Karten-Blätter aus einem Standarddeck mit zweiundfünfzig Karten berechnen als:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 \wähle 5}={\frac {52\mal 51\mal 50\mal 49\mal 48}{5\mal 4\mal 3\mal 2\mal 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Alternativ kann man die Formel in Form von Faktoren verwenden und die Faktoren im Zähler gegen Teile der Faktoren im Nenner aufheben, wonach nur die Multiplikation der verbleibenden Faktoren erforderlich ist:
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle {\begin{alignedat}{2}{52 \wähle 5}&={\frac {52!}{5!47!}}\\&={\frac {52\zeiten 51\zeiten 50\zeiten 49\zeiten 48\zeiten {\cancel {47!}}}{5\zeiten 4\zeiten 3\zeiten 2\zeiten {\cancel {1}}\zeiten {\cancel {47!}}}}\\&={\frac {52\Zeiten 51\Zeiten 50\Zeiten 49\Zeiten 48}{5\Zeiten 4\Zeiten 3\Zeiten 2}}\\&={\frac {(26\Zeiten {\Abbruch {2}})\Zeiten (17\Zeiten {\Abbruch {3})\Zeiten (10\Zeiten {\Abbruch {5})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}\times {\cancel {2}}}}\\&={26\times 17\times 10\times 49\times 12}\&=2{,}598{,}960.\end{alignedat}}
Eine weitere alternative Berechnung, die der ersten gleichwertig ist, beruht auf der Schreibweise
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \wählen k}={\frac {(n-0)}{1}}\mal {\frac {(n-1)}{2}}\mal {\frac {(n-2)}{3}}\mal \cdots {\frac {(n-(k-1))}{k}},}
was
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2.598 ergibt,960 {\displaystyle {52 \chose 5}={\frac {52}{1}}\mal {\frac {51}{2}}\mal {\frac {50}{3}}\mal {\frac {49}{4}}\mal {\frac {48}{5}}=2{,}598{,}960}
.
Wenn man dies in der folgenden Reihenfolge auswertet, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, kann dies nur mit ganzzahliger Arithmetik berechnet werden. Der Grund dafür ist, dass bei jeder Division das entstehende Zwischenergebnis selbst ein Binomialkoeffizient ist, so dass keine Reste auftreten.
Wenn man die symmetrische Formel in Bezug auf die Fakultäten ohne Vereinfachungen verwendet, ergibt sich eine recht umfangreiche Berechnung:
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {\begin{aligned}{52 \chose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}}
Aufzählung von k-KombinationenBearbeiten
Man kann alle k-Kombinationen einer gegebenen Menge S von n Elementen in einer festen Reihenfolge aufzählen, was eine Bijektion von einem Intervall von ( n k ) {\displaystyle {\tbinom {n}{k}}}
ganzer Zahlen mit der Menge dieser k-Kombinationen. Unter der Annahme, dass S selbst geordnet ist, z. B. S = { 1, 2, …, n }, gibt es zwei natürliche Möglichkeiten, die k-Kombinationen zu ordnen: indem man ihre kleinsten Elemente zuerst vergleicht (wie in den Abbildungen oben) oder indem man ihre größten Elemente zuerst vergleicht. Die letztere Möglichkeit hat den Vorteil, dass das Hinzufügen eines neuen größten Elements zu S den Anfangsteil der Aufzählung nicht verändert, sondern nur die neuen k-Kombinationen der größeren Menge nach den vorherigen hinzugefügt werden. Durch Wiederholung dieses Prozesses kann die Aufzählung unendlich mit k-Kombinationen von immer größeren Mengen erweitert werden. Wenn außerdem die Intervalle der ganzen Zahlen bei 0 beginnen, kann die k-Kombination an einer bestimmten Stelle i in der Aufzählung leicht aus i berechnet werden, und die so erhaltene Bijektion ist als kombinatorisches Zahlensystem bekannt. In der Computermathematik ist sie auch als „Rang“/“Ranking“ und „Unranking“ bekannt.
Es gibt viele Möglichkeiten, k Kombinationen aufzuzählen. Eine Möglichkeit ist, alle Binärzahlen kleiner als 2n zu besuchen. Man wählt diejenigen Zahlen aus, die k Bits ungleich Null haben, obwohl dies selbst für kleine n sehr ineffizient ist (z.B. würde n = 20 den Besuch von etwa einer Million Zahlen erfordern, während die maximale Anzahl der erlaubten k Kombinationen etwa 186 Tausend für k = 10 beträgt). Die Positionen dieser 1-Bits in einer solchen Zahl sind eine bestimmte k-Kombination aus der Menge { 1, …, n }. Eine andere einfache und schnellere Möglichkeit besteht darin, k Indexnummern der ausgewählten Elemente zu verfolgen, beginnend mit {0 … k-1} (nullbasiert) oder {1 .. k} (einbasig) als erste erlaubte k-Kombination und dann wiederholt zur nächsten erlaubten k-Kombination überzugehen, indem man die letzte Indexnummer erhöht, wenn sie kleiner als n-1 (nullbasig) oder n (einbasig) ist, oder die letzte Indexnummer x, die kleiner als die folgende Indexnummer minus eins ist, wenn ein solcher Index existiert, und die Indexnummern nach x auf {x+1, x+2, …} zurücksetzt.