Permutace a kombinace matematiky

Permutace a kombinace, různé způsoby, kterými mohou být objekty ze sady vybrány, obecně bez náhrady, pro vytvoření podmnožin. Tento výběr podmnožin se nazývá permutace, když je pořadí výběru faktorem, kombinace, když pořadí není faktorem. Francouzští matematici Blaise Pascal a Pierre de Fermat přihlíželi k poměru počtu požadovaných podmnožin k počtu všech možných podmnožin pro mnoho hazardních her v 17. století a podněcovali vývoj kombinatoriky a teorie pravděpodobnosti.

kombinatorika: Binomické koeficienty

n objekty se nazývají permutace n věcí pořízených r najednou. Počet permutací je

Koncepty a rozdíly mezi permutacemi a kombinacemi lze ilustrovat zkoumáním všech různých způsobů, kterými lze vybrat dvojici objektů z pěti rozlišitelných objektů - jako jsou písmena A, B, C, D a E. Pokud oba jsou zvažována vybraná písmena a pořadí výběru, pak je možné následujících 20 výsledků:

Každý z těchto 20 různých možných výběrů se nazývá permutace. Zejména se nazývají permutace pěti předmětů odebraných po dvou, a počet těchto permutací možných je označován symbolem ₅ P ₂, číst „5 permutaci 2.“ Obecně platí, že v případě, že jsou k dispozici n objektů, z nichž pro výběr a permutace (P) mají být vytvořeny s použitím K objektů najednou, počet možných různých permutací je označován symbolem _n P _k. Vzorec pro jeho vyhodnocení je _n P _k = n! / (N - k)! Výraz n! - číst „n faktoriál“ - znamená, že všechna po sobě jdoucí kladná celá čísla od 1 do včetně včetně n musí být vynásobena dohromady, a 0! je definována jako rovná 1. Například pomocí tohoto vzorce je počet permutací pěti objektů pořízených dva najednou

(Pro k = n, _n P _k = n! Pro 5 objektů tedy existuje 5! = 120 uspořádání.)

Pro kombinace se k objekty vyberou ze sady n objektů, aby se vytvořily podmnožiny bez objednání. V kontrastu s předchozím permutačním příkladem s odpovídající kombinací již nejsou podmnožiny AB a BA výraznými výběry; vyloučením takových případů zůstává pouze 10 různých možných podmnožin - AB, AC, AD, AE, BC, BD, BE, CD, CE a DE.

Počet takových podmnožin je označen _n C _k, přečtěte si „n zvolte k.“ Pro kombinace, protože k objekty mají k! uspořádání, jsou k! nerozlišitelné permutace pro každou volbu k objektů; proto dělíme permutační vzorec k! poskytuje následující kombinovaný vzorec:

Toto je stejné jako (n, k) binomický koeficient (viz binomická věta). Například počet kombinací pěti objektů pořízených po dvou je současně

Vzorce pro _n P _k a _n C _k se nazývají počítání vzorce, protože mohou být použity k počítání počtu možných permutací a kombinací v dané situaci, aniž by je všechny.