Permutacije i kombinacije, razni načini na koje se predmeti iz skupa mogu birati, uglavnom bez zamjene, radi stvaranja podskupova. Ovaj odabir podskupina naziva se permutacijom kada je redoslijed odabira faktor, kombinacija kad poredak nije faktor. Razmatrajući omjer broja željenih podskupova i broja svih mogućih podskupova za mnoge igre na sreću u 17. stoljeću, francuski matematičari Blaise Pascal i Pierre de Fermat dali su poticaj razvoju kombinatorike i teorije vjerojatnosti.
kombinatorika: Binomni koeficijenti
n predmeta naziva se permutacija od n stvari uzetih r istovremeno. Broj permutacija je
Pojmovi i razlike između permutacija i kombinacija mogu se ilustrirati ispitivanjem svih različitih načina na koje se par objekata može odabrati iz pet različivih objekata - kao što su slova A, B, C, D i E. Ako su oba odabrana su slova i redoslijed odabira, tada su moguća sljedeća 20 ishoda:
Svaki od tih 20 različitih mogućih odabira naziva se permutacijom. Konkretno, oni se nazivaju permutacijama pet objekata uzetih po dva, a broj takvih mogućih permutacija označava se simbolom 5 P 2, koji glasi „5 permuta 2.“ Općenito, ako je na raspolaganju n objekata iz kojih trebate izabrati, a permutacije (P) treba formirati pomoću k objekata odjednom, broj različitih mogućih permutacija označava se simbolom n P k. Formula za njegovu procjenu je n P k = n! / (N - k)! Izraz n! - glasi "n faktografski" - označava da se svi uzastopni pozitivni brojevi od 1 do uključujući n moraju množiti zajedno, i 0! definira se na jednak 1. Na primjer, koristeći ovu formulu, broj permutacija pet objekata uzetih dva istovremeno
(Za k = n, n P k = n! Dakle, za 5 objekata postoji 5! = 120 aranžmana.)
Za kombinacije, k objektivi su odabrani iz skupa od n objekata za proizvodnju podskupina bez naređivanja. U usporedbi s prethodnim primjerom permutacije s odgovarajućom kombinacijom, podskupine AB i BA više nisu različiti odabiri; uklanjanjem takvih slučajeva ostaje samo 10 različitih mogućih podskupova - AB, AC, AD, AE, BC, BD, BE, CD, CE i DE.
Broj takvih podskupova označen je s n C k, a glasi "n izaberi k". Za kombinacije, budući da k objekti imaju k! aranžmani, ima k! nerazlučive permutacije za svaki izbor k objekata; stoga dijelimo formulu permutacije s k! daje sljedeću kombinacijsku formulu:
To je isto kao (n, k) binomni koeficijent (vidi binomni teorem). Na primjer, broj kombinacija pet predmeta uzetih dva istodobno je
Formule za n P k i n C k nazivaju se formulama za brojanje, jer se mogu upotrijebiti za prebrojavanje broja mogućih permutacija ili kombinacija u određenoj situaciji, a da ih ne morate nabrajati.
