Permutace a Kombinace

Počítání Uspořádání a Výběrů ze Skupiny

Permutace (nPr) počítá, kolika způsoby lze uspořádat r položek z n, kde na pořadí záleží, zatímco kombinace (nCr) počítá, kolika způsoby lze vybrat r položek z n, kde na pořadí nezáleží. Zadejte celkový počet položek (n) a kolik vybíráte (r), a tato kalkulačka najde obě související odpovědi najednou.

Formule

• Permutace: $P(\vA{n}, \vB{r}) = \frac{\vA{n}!}{(\vA{n} - \vB{r})!}$ — ekvivalentně, součin $\vB{r}$ klesajících čísel počínaje $\vA{n}$: $\vA{n} \times (\vA{n}-1) \times \cdots \times (\vA{n}-\vB{r}+1)$.
• Kombinace: $C(\vA{n}, \vB{r}) = \frac{P(\vA{n}, \vB{r})}{\vB{r}!}$ — stejný počet permutací, dělený $\vB{r}!$ způsoby, kterými by mohly být samotné tyto $\vB{r}$ položky přeuspořádány (protože na pořadí u kombinace nezáleží).

Řešený Příklad

Výběr 3 položek ze skupiny 10, kde na pořadí záleží (permutace):

$$P(10,3) = 10 \times 9 \times 8 = 720$$

Stejný výběr, kde na pořadí NEZÁLEŽÍ (kombinace):

$$C(10,3) = 720 \div 3! = 720 \div 6 = 120$$

Kontrola ze Skutečného Světa

Šance na shodu všech 6 čísel v loterijním losování 6-z-49 je 1 ku C(49,6) — přesně 13 983 816 — protože pořadí, ve kterém jsou čísla vylosována, nemění, zda jste vyhráli.

Klíčové Faktory ke Zvážení

• Zda na pořadí záleží, je jedinou otázkou, která určuje, který vzorec platí. Uspořádání vítězů medailí na stupních vítězů (na 1., 2., 3. místě záleží) je problém permutace, zatímco výběr, kteří 3 lidé tvoří výbor (bez zapojeného pořadí) je problém kombinace — správná identifikace tohoto rozdílu je nejběžnějším zdrojem chyby při aplikaci těchto vzorců.
• Kombinace vždy vytváří stejný nebo menší počet než permutace pro stejné n a r. Protože kombinace seskupuje každé možné uspořádání stejných r položek do jednoho počtu, C(n,r) je vždy P(n,r) dělené r! — obě hodnoty se přesně shodují pouze tehdy, když je r 0 nebo 1, protože existuje jen jeden způsob, jak uspořádat 0 nebo 1 položku bez ohledu na pořadí.
• Počty permutací i kombinací rostou extrémně rychle, jak n a r rostou. Tento explozivní růst (nazývaný kombinatorická exploze) je přesně důvod, proč se šance ve stylu loterie stávají tak astronomicky malé jen s mírným nárůstem toho, z kolika čísel se losuje — přechod z loterie 6-z-49 na loterii 6-z-59, například, smysluplně zhoršuje šance i přes to, že fond roste jen o 10 čísel.
• Tyto vzorce předpokládají, že každá položka je odlišná a žádná nemůže být vybrána víc než jednou. Scénář umožňující opakovaný výběr (jako 4místný PIN, kde se číslice mohou opakovat) používá zcela odlišný vzorec počítání — vždy potvrďte, zda je opakování povoleno, než zde aplikujete standardní vzorce nPr/nCr.

Časté Chyby

• Použití počtu permutací, když na pořadí skutečně nezáleží, nebo naopak. Toto je nejčastější chyba — vždy se nejprve zeptejte, zda by prohození dvou vybraných položek znamenalo jiný výsledek, než zvolíte vzorec, místo hádání podle formulace úlohy.
• Zapomenutí, že kombinace nejsou nikdy větší než permutace pro stejné n a r. Pokud počet kombinací vyjde větší než odpovídající počet permutací pro stejné vstupy, něco bylo zadáno špatně — kombinace snižují počet permutací dělením, nikdy jej nezvyšují.
• Aplikování těchto vzorců na situaci, která umožňuje opakované výběry. Oba vzorce předpokládají, že každou položku lze vybrat nejvýše jednou — úloha umožňující opakování (jako generování 4místného PINu) potřebuje zcela jiný přístup k počítání, ne nPr nebo nCr.

Užitečné Vědět

• Chcete skutečně vypočítat pravděpodobnost konkrétního výsledku, ne jen spočítat možnosti? Kalkulačka Pravděpodobnosti promění počet kombinací nebo permutací ve skutečnou pravděpodobnost.
• Pracujete s celým datovým souborem místo pouhého počítání uspořádání? Kalkulačka Statistiky vypočítá průměr, směrodatnou odchylku a další souhrnné údaje ze seznamu čísel.
• Potřebujete zjednodušit poměr nebo najít společného jmenovatele jako součást související kombinatorické úlohy? Kalkulačka Největšího Společného Dělitele a Nejmenšího Společného Násobku najde největšího společného dělitele a nejmenší společný násobek množiny čísel.