Permutácie a kombinácie, rôzne spôsoby, akými môžu byť objekty zo sady vybrané, spravidla bez náhrady, na vytvorenie podmnožín. Tento výber podmnožín sa nazýva permutácia, keď poradie výberu je faktor, kombinácia, keď poradie nie je faktorom. Francúzski matematici Blaise Pascal a Pierre de Fermat podnietili vývoj počtu kombinácií a teórie pravdepodobnosti tým, že zvážili pomer počtu požadovaných podmnožín k počtu všetkých možných podmnožín pre mnoho hazardných hier v 17. storočí.
kombinatorika: Binomické koeficienty
n objektov sa nazýva permutácia n vecí odobratých naraz. Počet permutácií je
Koncepcie a rozdiely medzi permutáciami a kombináciami môžu byť ilustrované skúmaním všetkých rôznych spôsobov, ktorými je možné pár objektov vybrať z piatich rozpoznateľných objektov - napríklad písmen A, B, C, D a E. Ak obidve berú sa do úvahy vybrané písmená a poradie výberu, potom je možné dosiahnuť týchto 20 výsledkov:
Každý z týchto 20 rôznych možných výberov sa nazýva permutácia. Najmä sa nazývajú permutácie piatich predmetov odobratých po dvoch, a počet týchto permutácií možných je označovaný symbolom 5 P 2, čítať "5 permutáciu 2." Všeobecne platí, že v prípade, že sú k dispozícii n objektov, z ktorých pre výber a permutácie (P) majú byť vytvorené s použitím K objektov naraz, počet možných rôznych permutácií je označovaný symbolom n P k. Vzorec pre jeho hodnotenie je n P k = n! / (N - k)! Výraz n! - neprečítaný „n faktoriálny“ - znamená, že všetky po sebe idúce kladné celé čísla od 1 do vrátane vrátane n sa majú vynásobiť spolu, a 0! je definovaný ako rovný 1. Napríklad pomocou tohto vzorca je počet permutácií piatich predmetov braných dva naraz
(Pre k = n, n P k = n! Takže pre 5 objektov existuje 5! = 120 usporiadaní.)
Pre kombinácie sú k objekty vybrané zo sady n objektov, aby sa vytvorili podskupiny bez usporiadania. Na rozdiel od predchádzajúceho permutačného príkladu so zodpovedajúcou kombináciou už podskupiny AB a BA už nie sú zreteľnými výbermi; odstránením takýchto prípadov zostáva iba 10 rôznych možných podmnožín - AB, AC, AD, AE, BC, BD, BE, CD, CE a DE.
Počet takýchto podmnožín je označený n C k, prečítajte si „n zvoľte k“. Pre kombinácie, pretože k objekty majú k! aranžmány, sú k! nerozoznateľné permutácie pre každý výber objektov k; preto delíme permutačný vzorec k! poskytuje tento kombinovaný vzorec:
Je to rovnaké ako binomický koeficient (n, k) (pozri binomickú vetu). Napríklad počet kombinácií piatich predmetov zhotovených po dvoch je
Vzorce pre n P k a n C k sa nazývajú počítanie vzorca, pretože môžu byť použité na počítanie počtu možných permutácií a kombinácií v danej situácii, bez toho aby ich všetky.
