Het aantal k-combinaties uit een gegeven verzameling S van n elementen wordt in teksten over elementaire combinatoriek vaak aangeduid met C ( n , k ) {Displaystyle C(n,k)}
, of met een variant zoals C k n {{k}^{n}}
, n C k {C_{n}C_{k}}
, n C k {{k}^{n}C_{k}}
, C n , k {Displaystyle C_{n,k}}
of zelfs C n k {\displaystyle C_{n}^{k}}
(de laatste vorm was standaard in Franse, Roemeense, Russische, Chinese en Poolse teksten). Hetzelfde getal komt echter in vele andere wiskundige contexten voor, waar het wordt aangeduid met ( n k ) {Displaystyle {\tbinom {n}{k}}
(vaak gelezen als “n kiest k”); het komt met name voor als coëfficiënt in de binomiaalformule, vandaar de naam binomiaalcoëfficiënt. Men kan ( n k ) definiëren {{k}}
voor alle natuurlijke getallen k in één keer door de relatie ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}==\sum _{k\geq 0}{tbinom {n}{k}X^{k},}
waaruit blijkt dat
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}=1,}
en voorts dat
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
voor k > n.
Om te zien dat deze coëfficiënten k-combinaties uit S tellen, kan men eerst een verzameling van n verschillende variabelen Xs beschouwen, gelabeld met de elementen s van S, en het product uitbreiden over alle elementen van S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle _{s}in S}(1+X_{s});}
het heeft 2n verschillende termen die corresponderen met alle deelverzamelingen van S, waarbij elke deelverzameling het product geeft van de overeenkomstige variabelen Xs. Door nu alle Xs gelijk te stellen aan de ongelabelde variabele X, zodat het product (1 + X)n wordt, wordt de term voor elke k-combinatie uit S Xk, zodat de coëfficiënt van die macht in het resultaat gelijk is aan het aantal van dergelijke k-combinaties.
Binomiale coëfficiënten kunnen op verschillende manieren expliciet worden berekend. Om ze allemaal te krijgen voor de expansies tot en met (1 + X)n kan men (naast de reeds gegeven basisgevallen) de recursierelatie
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) gebruiken, {\displaystyle {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
voor 0 < k < n, die volgt uit (1 + X)n = (1 + X)n – 1(1 + X); dit leidt tot de constructie van de driehoek van Pascal.
Voor het bepalen van een individueel binomiaal coëfficiënt is het praktischer om de formule
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}
.
De teller geeft het aantal k-permutaties van n, d.w.z, van reeksen van k verschillende elementen van S, terwijl de noemer het aantal van dergelijke k-permutaties geeft die dezelfde k-combinatie geven als de volgorde wordt genegeerd.
Wanneer k groter is dan n/2, bevat de bovenstaande formule factoren die zowel de teller als de noemer gemeen hebben, en door ze weg te strepen ontstaat de relatie
( n k ) = ( n n – k ) , {{1686>
voor 0 ≤ k ≤ n. Dit drukt een symmetrie uit die duidelijk blijkt uit de binomiale formule, en kan ook worden begrepen in termen van k-combinaties door het complement te nemen van zo’n combinatie, die een (n – k)-combinatie is.
Eindelijk is er een formule die deze symmetrie rechtstreeks vertoont, en de verdienste heeft dat ze gemakkelijk te onthouden is:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {n}{k}={\frac {n!}{k!(n-k)!},}
waar n! de factorie van n aanduidt. Deze formule wordt verkregen uit de vorige formule door de noemer en teller te vermenigvuldigen met (n – k)!
De laatste formule kan direct begrepen worden, door de n! permutaties van alle elementen van S te beschouwen. Elke permutatie geeft een k-combinatie door de eerste k elementen te kiezen. Er zijn veel dubbele selecties: elke gecombineerde permutatie van de eerste k elementen onder elkaar, en van de laatste (n – k) elementen onder elkaar geeft dezelfde combinatie; dit verklaart de deling in de formule.
Uit de bovenstaande formules volgen relaties tussen aangrenzende getallen in de driehoek van Pascal in alle drie de richtingen:
( n k ) = { ( n k – 1 ) n – k + 1 k als k > 0 ( n – 1 k ) n n – k als k < n ( n – 1 k – 1 ) n k als 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 {ntext{if }}k<n}{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {ntext{if }}n,k>0\end{cases}}}
.
Tezamen met de basisgevallen ( n 0 ) = 1 = ( n n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}
, hiermee kunnen achtereenvolgens alle aantallen combinaties uit eenzelfde verzameling (een rij in de driehoek van Pascal), van k-combinaties van verzamelingen van toenemende grootte, en van combinaties met een complement van vaste grootte n – k worden berekend.
Voorbeeld van het tellen van combinatiesEdit
Als specifiek voorbeeld kan men het aantal mogelijke handen van vijf kaarten uit een standaard spel van tweeënvijftig kaarten berekenen als:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 maal 5}={\frac {52 maal 51 maal 50 maal 49 maal 48}{5 maal 4 maal 3 maal 2 maal 1}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Als alternatief kan men de formule in termen van factoren gebruiken en de factoren in de teller opheffen tegen delen van de factoren in de noemer, waarna slechts de vermenigvuldiging van de overblijvende factoren vereist is:
( 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. {Begin{uitgelijnd}{2}{52}{5,47}}&={52,51}{5,47}}&={52,51}{50,50}{48,48}{5,4}{5,4}{2,5}{5,5}{5,5}{5,1}}{47!}}}}&={\frac {52 maal 51 maal 50 maal 49 maal 48}{5 maal 4 maal 3 maal 2}}{\9782>={\frac {(26 maal 2})\t maal (17 maal 3})\t maal (10 maal 4}{5}} {5}})\times 49} times (12}\times {4}})}{\times {4}}\times {3}}\times {2}}={26}\times 17}\times 10}\times 49}\times 12}\times&=2{,}598{,}960.\einde{alignedat}}
Een andere alternatieve berekening, gelijkwaardig aan de eerste, berust op het schrijven van
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times {\dots \times {\frac {(n-(k-1))}{k}},}
wat geeft
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52}{5}={\frac {52}{1}} keer {\frac {51}{2}} keer {\frac {50}{3}} keer {\frac {49}{4}} keer {\frac {48}{5}}=2{,}598{,}960}
.
Wanneer dit in de volgende volgorde wordt geëvalueerd, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, kan dit worden berekend met alleen integer rekenen. De reden is dat bij elke deling het tussenresultaat dat ontstaat zelf een binomiaal coëfficiënt is, zodat er nooit resten optreden.
Opgave van de symmetrische formule in termen van factorialen zonder vereenvoudigingen geeft een nogal uitgebreide berekening:
( 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 \choose 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.\einde{aligned}}
K-combinaties opsommenEdit
U kunt alle k-combinaties van een gegeven verzameling S van n elementen in een vaste volgorde opsommen, waardoor een bijectie ontstaat van een interval van ( n k ) {\displaystyle {\tbinom {n}{k}}
gehele getallen met de verzameling van die k-combinaties. Ervan uitgaande dat S zelf geordend is, bijvoorbeeld S = { 1, 2, …, n }, zijn er twee natuurlijke mogelijkheden om de k-combinaties te ordenen: door eerst de kleinste elementen te vergelijken (zoals in de illustraties hierboven) of door eerst de grootste elementen te vergelijken. De laatste optie heeft het voordeel dat het toevoegen van een nieuw grootste element aan S het initiële deel van de opsomming niet verandert, maar gewoon de nieuwe k-combinaties van de grotere verzameling toevoegt na de vorige. Door dit proces te herhalen, kan de opsomming oneindig uitgebreid worden met k-combinaties van steeds grotere verzamelingen. Als bovendien de intervallen van de gehele getallen worden genomen om te beginnen bij 0, dan kan de k-combinatie op een gegeven plaats i in de opsomming gemakkelijk worden berekend uit i, en de zo verkregen bijectie is bekend als het combinatorische getallenstelsel. Het is ook bekend als “rang”/”ranking” en “unranking” in de computationele wiskunde.
Er zijn vele manieren om k combinaties op te sommen. Eén manier is om alle binaire getallen kleiner dan 2n te doorlopen. Kies die getallen met k niet-nul bits, hoewel dit zelfs voor kleine n zeer inefficiënt is (b.v. n = 20 zou het bezoeken van ongeveer een miljoen getallen vereisen, terwijl het maximum aantal toegestane k combinaties ongeveer 186 duizend is voor k = 10). De posities van deze 1 bits in zo’n getal is een specifieke k-combinatie van de verzameling { 1, …, n }. Een andere eenvoudige, snellere manier is het bijhouden van k-indexnummers van de geselecteerde elementen, te beginnen met {0 .. k-1} (op nul gebaseerd) of {1 .. k} (op basis van één) als de eerste toegestane k-combinatie en dan herhaaldelijk naar de volgende toegestane k-combinatie door het laatste indexcijfer te verhogen als het lager is dan n-1 (op basis van nul) of n (op basis van één) of het laatste indexcijfer x dat lager is dan het indexcijfer dat er op volgt min één als zo’n index bestaat en de indexcijfers na x te resetten naar {x+1, x+2, …}.