Počet k-kombinací z dané množiny S o n prvcích se v textech elementární kombinatoriky často označuje C ( n , k ) {\displaystyle C(n,k)}
, nebo variantou jako 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}}
nebo dokonce C n k {\displaystyle C_{n}^{k}}
(tato druhá forma byla standardní ve francouzských, rumunských, ruských, čínských a polských textech). Stejné číslo se však vyskytuje v mnoha dalších matematických kontextech, kde se označuje ( n k ) {\displaystyle {\tbinom {n}{k}}}.
(často se čte jako „n zvolte k“); zejména se vyskytuje jako koeficient v binomickém vzorci, odtud jeho název binomický koeficient. Lze definovat ( n k ) {\displaystyle {\tbinom {n}{k}}}.
pro všechna přirozená čísla k najednou vztahem ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}
z čehož je jasné, že
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}
a dále,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
pro k > n.
Abychom viděli, že tyto koeficienty počítají k-kombinace z S, můžeme nejprve uvažovat soubor n různých proměnných Xs označených prvky s S a součin rozložit na všechny prvky S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
má 2n různých členů odpovídajících všem podmnožinám S, přičemž každá podmnožina dává součin příslušných proměnných Xs. Nyní stanovíme, že všechny Xs jsou rovny neoznačené proměnné X, takže součin nabývá hodnoty (1 + X)n, člen pro každou k-kombinaci z S nabývá hodnoty Xk, takže koeficient této mocniny ve výsledku se rovná počtu takových k-kombinací.
Koeficienty binomů lze explicitně vypočítat různými způsoby. K získání všech pro rozklady do (1 + X)n lze (kromě již uvedených základních případů) použít rekurzivní vztah
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
pro 0 < k < n, což vyplývá z (1 + X)n = (1 + X)n – 1(1 + X); to vede ke konstrukci Pascalova trojúhelníku.
Pro určení individuálního binomického koeficientu je praktičtější použít vzorec
( 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!}}}
.
Čitatel udává počet k-permutací n, tj, posloupností k různých prvků S, zatímco jmenovatel udává počet takových k-permutací, které dávají stejnou k-kombinaci při zanedbání pořadí.
Když je k větší než n/2, výše uvedený vzorec obsahuje činitele společné čitateli i jmenovateli a jejich zrušením získáme vztah
( n k ) = ( n n – k ) , {\displayystyle {\binom {n}{k}}={\binom {n}{n-k}},}
pro 0 ≤ k ≤ n. To vyjadřuje symetrii, která je zřejmá z binomického vzorce, a lze ji také pochopit z hlediska k-kombinací tak, že vezmeme doplněk takové kombinace, což je (n – k)-kombinace.
Nakonec existuje vzorec, který tuto symetrii vykazuje přímo a má tu výhodu, že je snadno zapamatovatelný:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}
kde n! označuje faktoriál n. Získáme ho z předchozího vzorce vynásobením jmenovatele a čitatele (n – k)!, takže je jistě výpočetně méně efektivní než tento vzorec.
Poslední vzorec lze chápat přímo tak, že uvažujeme n! permutací všech prvků S. Každá taková permutace dává k-kombinaci výběrem jejích prvních k prvků. Existuje mnoho duplicitních výběrů: každá kombinovaná permutace prvních k prvků mezi sebou a posledních (n – k) prvků mezi sebou dává tutéž kombinaci; to vysvětluje dělení ve vzorci.
Z výše uvedených vzorců vyplývají vztahy mezi sousedními čísly v Pascalově trojúhelníku ve všech třech směrech:
( n k ) = { ( n k – 1 ) n – k + 1 k pokud k > 0 ( n – 1 k ) n n – k pokud k < n ( n – 1 k – 1 ) n k pokud 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}}}
.
Společně se základními případy ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}}
, umožňují postupně vypočítat všechny počty kombinací z téže množiny (řádek v Pascalově trojúhelníku), k-kombinací množin rostoucí velikosti a kombinací s doplňkem pevné velikosti n – k.
Příklad počítání kombinacíUpravit
Jako konkrétní příklad lze vypočítat počet možných kombinací pěti karet ze standardního balíčku padesáti dvou karet jako:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311 875 200 120 = 2 598 960. {\displaystyle {52 \výběr 5}={\frac {52\časů 51\časů 50\časů 49\časů 48}{5\časů 4\časů 3\časů 2\časů 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Alternativně lze použít vzorec ve smyslu faktoriálů a zrušit činitele v čitateli proti částem činitelů ve jmenovateli, načež je třeba pouze vynásobit zbývající činitele:
( 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.\konec{zarovnání}}
Další alternativní výpočet, ekvivalentní prvnímu, je založen na zápisu
( 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 {(n-(k-1))}{k}},}
což dává
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52 \zvolte 5}={\frac {52}{1}}krát {\frac {51}{2}}krát {\frac {50}{3}}krát {\frac {49}{4}}krát {\frac {48}{5}}=2{,}598{,}960}
.
Při vyhodnocení v následujícím pořadí 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 lze tento výpočet provést pouze pomocí celočíselné aritmetiky. Důvodem je, že při každém dělení je vzniklý mezivýsledek sám o sobě binomickým koeficientem, takže nikdy nevznikají žádné zbytky.
Při použití symetrického vzorce ve smyslu faktoriálů bez provedení zjednodušení získáme poměrně rozsáhlý výpočet:
( 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}}
Vyčíslení k-kombinacíEdit
Můžeme vyčíslit všechny k-kombinace dané množiny S o n prvcích v nějakém pevném pořadí, které stanoví bijekci z intervalu ( n k ) {\displaystyle {\tbinom {n}{k}}}.
celých čísel s množinou těchto k-kombinací. Za předpokladu, že S je sám o sobě uspořádaný, například S = { 1, 2, …, n }, existují dvě přirozené možnosti uspořádání jeho k-kombinací: tak, že se nejprve porovnají jejich nejmenší prvky (jako na obrázcích výše), nebo tak, že se nejprve porovnají jejich největší prvky. Druhá možnost má tu výhodu, že přidáním nového největšího prvku do S se nezmění počáteční část výčtu, ale pouze se přidají nové k-kombinace větší množiny za předchozí. Opakováním tohoto postupu lze výčet rozšiřovat donekonečna o k-kombinace stále větších množin. Pokud navíc intervaly celých čísel bereme tak, že začínají na 0, pak lze z i snadno vypočítat k-kombinaci na daném místě i ve výčtu a takto získaná bijekce je známá jako kombinatorická číselná soustava. Ve výpočetní matematice je také známá jako „rank“/“ranking“ a „unranking“.
Existuje mnoho způsobů, jak vyčíslit k kombinací. Jedním ze způsobů je navštívit všechna binární čísla menší než 2n. Vybrat ta čísla, která mají k nenulových bitů, i když je to velmi neefektivní i pro malé n (např. n = 20 by vyžadovalo navštívit asi milion čísel, zatímco maximální počet povolených k kombinací je pro k = 10 asi 186 tisíc). Pozice těchto 1 bitů v takovém čísle je konkrétní k-kombinace množiny { 1, …, n }. Dalším jednoduchým a rychlejším způsobem je sledování k indexových čísel vybraných prvků, počínaje {0 .. k-1}. (s nulou) nebo {1 .. k}. (na základě jedničky) jako první přípustnou k-kombinaci a pak opakovaně přecházet na další přípustnou k-kombinaci zvyšováním posledního indexového čísla, pokud je menší než n-1 (na základě nuly) nebo n (na základě jedničky), nebo posledního indexového čísla x, které je menší než následující indexové číslo minus jedna, pokud takový index existuje, a obnovením indexových čísel za x na {x+1, x+2, …}.