Záleží na pořadí? To je celá otázka

Kombinatorická úloha se rozhoduje dvěma otázkami, a jakmile na ně odpovíte, vzorec je daný:

  • Záleží na pořadí? Ano znamená variace, ne znamená kombinace.
  • Smí se prvky opakovat? Podle toho ta či ona verze vzorce.

Los ze šesti čísel je kombinace: na pořadí vytažení nezáleží. Heslo ze šesti znaků je variace s opakováním: záleží na pořadí a znaky se můžou opakovat. Pořadí běžců v cíli je permutace. Víc případů v podstatě není.

Proč se dělí faktoriálem

Variace se počítají snadno: na první místo je n možností, na druhé o jednu míň, a tak dál. Kombinace se z nich odvodí jediným krokem. Každou skupinu k prvků totiž variace započítají tolikrát, kolika způsoby jde těch k prvků seřadit, tedy k!krát. Vydělí se proto k! a je hotovo.

Odtud plyne i to, že kombinací je vždycky méně než variací, přesně k!krát.

Kombinační číslo a jeho symetrie

Platí C(n;k) = C(n;n-k), a není to početní trik. Vybrat k prvků je totéž jako rozhodnout, kterých n-k prvků zůstane. Prakticky se to vyplatí využít při počítání: C(49;46) se počítá mnohem snáz jako C(49;3).

Kalkulačka výše počítá násobením a dělením po krocích, ne třemi faktoriály. Čísla tak zůstanou malá a výsledek přesný i pro velká n.

Pascalův trojúhelník je tatáž čísla

Trojúhelník se čísluje od nuly a jeho n-tý řádek obsahuje právě kombinační čísla C(n;0) až C(n;n). Každé číslo uvnitř je součtem dvou nad ním, což odpovídá vztahu C(n;k) = C(n-1;k-1) + C(n-1;k): daný prvek buď vyberu, nebo ne, a jiná možnost není.

Součet každého řádku je mocnina dvojky. Není to náhoda: 2ⁿ je počet všech podmnožin n-prvkové množiny, a řádek je právě rozpis toho počtu podle velikosti podmnožiny.

Binomická věta

Rozvoj (a + b)ⁿ má n+1 členů, exponenty se v nich doplňují do n a koeficienty jsou přesně n-tý řádek Pascalova trojúhelníku. Důvod je kombinatorický: roznásobením n závorek vzniká každý člen tolikrát, kolika způsoby lze vybrat, ze kterých závorek se vezme b.

Počítá se přesně

Už 20! přesahuje to, co běžné desetinné číslo udrží přesně, a kombinační čísla přerostou stejně rychle. Všechno tady proto běží v celočíselné aritmetice bez omezení délky: 100! vyjde správně na poslední číslici, ne zaokrouhleně v exponenciálním tvaru. Stejnou volbu dělá i převodník číselných soustav, a ze stejného důvodu.