Antallet af k-kombinationer fra en given mængde S med n elementer betegnes ofte i tekster om elementær kombinatorik med C ( n , k ) {\displaystyle C(n,k)}
, eller med en variant som 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}} {\displaystyle C_{n,k}}
eller endda C n k {\displaystyle C_{n}^{k}}
(sidstnævnte form var standard i franske, rumænske, russiske, kinesiske og polske tekster). Det samme tal forekommer imidlertid i mange andre matematiske sammenhænge, hvor det betegnes med ( n k ) {\displaystyle {\tbinom {\tbinom {n}{k}}}}
(ofte læst som “n vælger k”); især forekommer det som en koefficient i binomialformlen, deraf navnet binomialkoefficient. Man kan definere ( n k ) {\displaystyle {\tbinom {\tbinom {n}{k}}}}
for alle naturlige tal k på én gang ved relationen ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}}X^{k}},}
heraf fremgår det, at
( n 0 ) = ( n n n ) = 1 , {\displaystyle {\binom {\binom {n}{0}}}}={\binom {n}{n}{n}}}=1,}
og endvidere,
( n k ) = 0 {\displaystyle {\binom {\binom {n}{k}}=0}
for k > n.
For at se, at disse koefficienter tæller k-kombinationer fra S, kan man først betragte en samling af n forskellige variabler Xs mærket med elementerne s i S, og udvide produktet over alle elementer i S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s}};}
det har 2n forskellige termer, der svarer til alle delmængder af S, idet hver delmængde giver produktet af de tilsvarende variabler Xs. Hvis man nu sætter alle Xs lig med den umærkede variabel X, således at produktet bliver (1 + X)n, bliver udtrykket for hver k-kombination fra S til Xk, således at koefficienten af denne potens i resultatet er lig med antallet af sådanne k-kombinationer.
Binomialkoefficienter kan beregnes eksplicit på forskellige måder. For at få alle dem for udvidelserne op til (1 + X)n kan man (ud over de allerede givne grundtilfælde) anvende rekursionsrelationen
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {\binom {n}{k}}}={\binom {n-1}{k-1}}}}+{\binom {n-1}{k}}},}
for 0 < k < n, hvilket følger af (1 + X)n = (1 + X)n – 1(1 + X); dette fører til konstruktionen af Pascals trekant.
Til bestemmelse af en individuel binomialkoefficient er det mere praktisk at anvende formlen
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {\binom {n}{k}}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}}}
.
Tælleren angiver antallet af k-permutationer af n, dvs, af sekvenser af k forskellige elementer af S, mens nævneren angiver antallet af sådanne k-permutationer, der giver den samme k-kombination, når der ses bort fra rækkefølgen.
Når k overstiger n/2, indeholder ovenstående formel faktorer, der er fælles for tælleren og nævneren, og hvis man ophæver dem, får man relationen
( n k ) = ( n n n – k ) , {\displaystyle {\binom {n}{k}}}={\binom {n}{n}{n-k}}},}
for 0 ≤ k ≤ n. Dette udtrykker en symmetri, der fremgår af binomialformlen, og som også kan forstås med hensyn til k-kombinationer ved at tage komplementet til en sådan kombination, som er en (n – k)-kombination.
Endeligt findes der en formel, der viser denne symmetri direkte, og som har den fordel, at den er let at huske:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {\binom {n}{k}}}={\frac {n!}{k!(n-k)!}}},}
hvor n! betegner faktorial af n. Den fås fra den foregående formel ved at multiplicere nævner og tæller med (n – k)!, så den er helt sikkert beregningsteknisk mindre effektiv end denne formel.
Den sidste formel kan forstås direkte ved at betragte de n! permutationer af alle elementerne i S. Hver sådan permutation giver en k-kombination ved at vælge de første k elementer. Der er mange dobbelte valg: enhver kombineret permutation af de første k elementer blandt hinanden og af de sidste (n – k) elementer blandt hinanden giver den samme kombination; dette forklarer opdelingen i formlen.
Fra ovenstående formler følger relationer mellem tilstødende tal i Pascals trekant i alle tre retninger:
( n k ) = { ( n k – 1 ) n – k + 1 k hvis k > 0 ( n – 1 k ) n n – k hvis k < n ( n – 1 k – 1 ) n k hvis n , k > 0 {\displaystyle {\binom {\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}}}
.
Sammen med de grundlæggende tilfælde ( n 0 ) = 1 = ( n n n ) {\displaystyle {\tbinom {n}{0}}}=1={\tbinom {n}{n}}}}
, giver disse mulighed for successiv beregning af henholdsvis alle antal kombinationer fra samme mængde (en række i Pascals trekant), af k-kombinationer af mængder af voksende størrelse og af kombinationer med et supplement af fast størrelse n – k.
Eksempel på optælling af kombinationerRediger
Som et konkret eksempel kan man beregne antallet af mulige hænder med fem kort fra et standardspil med 52 kort som:
( 52 5 ) = 52 × 51 × 50 × 49 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}}={\frac {311{,}875{,}200}{120}}}=2{,}598{,}960.}
Alternativt kan man bruge formlen i form af faktorialer og annullere faktorerne i tælleren mod dele af faktorerne i nævneren, hvorefter kun multiplikation af de resterende faktorer er nødvendig:
( 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 \vælger 5}&={\frac {52!}{5!47!}}}\\\&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}}\times {\cancel {47!}}}}\\\\&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}}\\\&={\frac {(26\times {\cancel {2}}})\times (17\times {\cancel {3}}})\times (10\times {\cancel {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}}}
En anden alternativ beregning, der svarer til den første, er baseret på at skrive
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \choose k}={\frac {(n-0)}{1}}}\times {\frac {(n-1)}{2}}}\times {\frac {(n-2)}{3}}}\times \cdots \times {\frac {\frac {(n-(k-1))}{k}}},}
hvilket giver
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52 \choose 5}={\frac {52}{1}}}\times {\frac {51}{2}}}\times {\frac {50}{3}}}\times {\frac {49}{4}}}\times {\frac {48}{5}}=2{,}598{,}960}
.
Ved evaluering i følgende rækkefølge, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, kan dette kun beregnes ved hjælp af heltalsaritmetik. Årsagen er, at når hver division finder sted, er det mellemresultat, der produceres, selv en binomialkoefficient, så der opstår aldrig nogen restkoefficienter.
Ved anvendelse af den symmetriske formel i form af faktorialer uden at foretage forenklinger fås en ret omfattende beregning:
( 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.\end{aligned}}}
Optælling af k-kombinationerRediger
Man kan opregne alle k-kombinationer af en given mængde S med n elementer i en vis fast rækkefølge, hvilket etablerer en bijektion fra et interval af ( n k ) {\displaystyle {\tbinom {\tbinom {n}{k}}}}
hele tal med mængden af disse k-kombinationer. Hvis man antager, at S i sig selv er ordnet, f.eks. S = { 1, 2, …, n }, er der to naturlige muligheder for at ordne dens k-kombinationer: ved at sammenligne deres mindste elementer først (som i illustrationerne ovenfor) eller ved at sammenligne deres største elementer først. Sidstnævnte mulighed har den fordel, at tilføjelse af et nyt største element til S ikke ændrer den indledende del af opregningen, men blot tilføjer de nye k-kombinationer i den større mængde efter de foregående. Ved at gentage denne proces kan opregningen udvides i det uendelige med k-kombinationer af stadig større mængder. Hvis man desuden antager, at de hele tals intervaller starter ved 0, kan k-kombinationen på et givet sted i i opregningen let beregnes ud fra i, og den således opnåede bijeksion er kendt som det kombinatoriske talsystem. Det er også kendt som “rank”/”ranking” og “unranking” i beregningsmatematik.
Der er mange måder at opregne k kombinationer på. En måde er at besøge alle de binære tal mindre end 2n. Vælg de tal, der har k bits, der ikke er nul, selv om dette er meget ineffektivt selv for små n (f.eks. ville n = 20 kræve at besøge ca. en million tal, mens det maksimale antal tilladte k kombinationer er ca. 186 tusinde for k = 10). Placeringen af disse 1-bits i et sådant tal er en specifik k-kombination af mængden { 1, …, n }. En anden enkel og hurtigere måde er at spore k indeksnumre for de valgte elementer, idet man starter med {0 … k-1} (nulbaseret) eller {1 … k} (et-baseret) som den første tilladte k-kombination og derefter gentagne gange gå til den næste tilladte k-kombination ved at øge det sidste indekstal, hvis det er lavere end n-1 (nulbaseret) eller n (et-baseret), eller det sidste indekstal x, der er mindre end indekstallet efter det minus et, hvis et sådant indekstal findes, og ved at nulstille indekstallene efter x til {x+1, x+2, …}.