Antalet k-kombinationer från en given mängd S med n element betecknas ofta i texter 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}}
eller till och med C n k {\displaystyle C_{n}^{k}}
(den senare formen var standard i franska, rumänska, ryska, kinesiska och polska texter). Samma tal förekommer dock i många andra matematiska sammanhang, där det betecknas med ( n k ) {\displaystyle {\tbinom {\n}{k}}}}
(ofta läst som ”n väljer k”); särskilt förekommer det som en koefficient i binomialformeln, därav namnet binomialkoefficient. Man kan definiera ( n k ) {\displaystyle {\tbinom {\tbinom {n}{k}}}}
för alla naturliga tal k på en gång genom relationen ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}}X^{k},}
varifrån det framgår att
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {\binom {n}{0}}}={\binom {n}{n}}}=1,}
och vidare,
( n k ) = 0 {\displaystyle {\binom {\binom {n}{k}}=0}
för k > n.
För att se att dessa koefficienter räknar k-kombinationer från S, kan man först betrakta en samling av n distinkta variabler Xs märkta med elementen s i S, och expandera produkten över alla element i S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
den har 2n distinkta termer som motsvarar alla delmängder av S, där varje delmängd ger produkten av motsvarande variabler Xs. Om man nu sätter alla Xs lika med den omärkta variabeln X, så att produkten blir (1 + X)n, blir termen för varje k-kombination från S Xk, så att koefficienten för den potensen i resultatet är lika med antalet sådana k-kombinationer.
Binomialkoefficienter kan beräknas explicit på olika sätt. För att få fram alla för expansionerna upp till (1 + X)n kan man (utöver de redan angivna grundfallen) använda rekursionsrelationen
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}}={\binom {n-1}{k-1}}}+{\binom {n-1}{k}}},}
för 0 < k < n, vilket följer av (1 + X)n = (1 + X)n – 1(1 + X); Detta leder till konstruktionen av Pascals triangel.
För att bestämma en individuell binomialkoefficient är det mer praktiskt att använda formeln
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {n}{k}}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}}}
.
Täljaren anger antalet k-permutationer av n, dvs, av sekvenser av k distinkta element i S, medan nämnaren anger antalet sådana k-permutationer som ger samma k-kombination när ordningen ignoreras.
När k överstiger n/2 innehåller ovanstående formel faktorer som är gemensamma för täljaren och nämnaren, och genom att upphäva dem får man relationen
( n k ) = ( n n n – k ) , {\displaystyle {\binom {n}{k}}}={\binom {n}{n}{n-k}},}
för 0 ≤ k ≤ n. Detta uttrycker en symmetri som framgår av binomialformeln, och kan också förstås i termer av k-kombinationer genom att ta komplementet till en sådan kombination, som är en (n – k)-kombination.
Slutligt finns det en formel som uppvisar denna symmetri direkt, och som har den förtjänsten att den är lätt att komma ihåg:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {\binom {n}{k}}}={\frac {n!}{k!(n-k)!}},}
där n! betecknar faktorn av n. Den erhålls från den föregående formeln genom att multiplicera nämnare och täljare med (n – k)!, så den är säkerligen beräkningsmässigt mindre effektiv än den formeln.
Den sista formeln kan förstås direkt genom att betrakta n! permutationer av alla element i S. Varje sådan permutation ger en k-kombination genom att välja de första k elementen. Det finns många dubbla val: varje kombinerad permutation av de första k elementen bland varandra och av de sista (n – k) elementen bland varandra ger samma kombination; detta förklarar uppdelningen i formeln.
Från ovanstående formler följer relationer mellan intilliggande tal i Pascals triangel i alla tre riktningar:
( n k ) = { ( n k – 1 ) n – k + 1 k om k > 0 ( n – 1 k ) n n – k om k < n ( n – 1 k – 1 ) n k om 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}}}
.
Samman med de grundläggande fallen ( n 0 ) = 1 = ( n n n ) {\displaystyle {\tbinom {n}{0}}}=1={\tbinom {n}{n}}}}
, möjliggör dessa successiva beräkningar av alla antal kombinationer från samma uppsättning (en rad i Pascals triangel), av k-kombinationer av uppsättningar av växande storlek och av kombinationer med ett komplement av fast storlek n – k.
Exempel på räkning av kombinationerRedigera
Som ett specifikt exempel kan man beräkna antalet möjliga händer med fem kort från en standardlek med 52 kort som:
( 52 5 ) = 52 × 51 × 50 × 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 använda formeln i termer av faktorier och upphäva faktorerna i täljaren mot delar av faktorerna i nämnaren, varefter endast multiplikation av de återstående faktorerna krävs:
( 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 \choose 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 annan alternativ beräkning, som är likvärdig med den första, bygger på att skriva
( 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 {\frac {(n-1)}{2}}}\times {\frac {(n-2)}{3}}}\times \cdots \times {\frac {(n-(k-1))}{k}},}
vilket ger
( 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}
.
När detta utvärderas i följande ordning, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, kan detta beräknas med hjälp av enbart heltalsaritmetik. Anledningen är att när varje division sker är det mellanresultat som produceras i sig självt en binomialkoefficient, så inga rester uppstår någonsin.
Användning av den symmetriska formeln i termer av faktorialer utan att utföra förenklingar ger en ganska omfattande beräkning:
( 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}}}
Uppräkning av k-kombinationerRedigera
Man kan räkna upp alla k-kombinationer av en given mängd S med n element i en bestämd ordning, vilket etablerar en bijection från ett intervall av ( n k ) {\displaystyle {\tbinom {n}{k}}}
med mängden av dessa k-kombinationer. Om man antar att S i sig självt är ordnat, till exempel S = { 1, 2, …, n }, finns det två naturliga möjligheter att ordna dess k-kombinationer: genom att jämföra deras minsta element först (som i illustrationerna ovan) eller genom att jämföra deras största element först. Det senare alternativet har den fördelen att ett nytt största element till S inte ändrar den inledande delen av uppräkningen, utan bara lägger till de nya k-kombinationerna i den större mängden efter de tidigare. Genom att upprepa denna process kan uppräkningen utökas i all oändlighet med k-kombinationer av allt större mängder. Om man dessutom antar att de hela talens intervall börjar vid 0, kan k-kombinationen på en given plats i i uppräkningen lätt beräknas från i, och den sålunda erhållna bijektionen är känd som det kombinatoriska talsystemet. Det är också känt som ”rank”/”ranking” och ”unranking” inom beräkningsmatematiken.
Det finns många sätt att räkna upp k kombinationer. Ett sätt är att besöka alla binära tal som är mindre än 2n. Välj de tal som har k bitar som inte är noll, även om detta är mycket ineffektivt även för små n (t.ex. skulle n = 20 kräva att man besöker ungefär en miljon tal medan det maximala antalet tillåtna k kombinationer är ungefär 186 tusen för k = 10). Placeringarna av dessa 1-bitar i ett sådant tal är en specifik k-kombination av mängden { 1, …, n }. Ett annat enkelt och snabbare sätt är att spåra k indexnummer för de valda elementen, med början med {0 … k-1} (nollbaserat) eller {1 … k} (enbaserat) som den första tillåtna k-kombinationen och sedan upprepade gånger gå till nästa tillåtna k-kombination genom att öka det sista indexnumret om det är lägre än n-1 (nollbaserat) eller n (enbaserat) eller det sista indexnumret x som är lägre än det efterföljande indexnumret minus ett om ett sådant index existerar och återställa indexnumren efter x till {x+1, x+2, …}.