Kombinatorika

Sjetimo se da je skup nekakva neuređena kolekcija elemenata. To znači da nema pravila kako su članovi složeni - možemo zamisliti da su svi razbacani u jednoj vreći.

Nasuprot njima, imamo uređene $k$-torke - nizove koji imaju $k$ mjesta (nizovi duljine $k$) koje punimo određenim elementima. U ovom slučaju se točno zna koji element je na prvom mjestu, koji na drugom itd. Elementi moraju biti različiti.

U kombinatorici se takva uređena $k$-torka zove varijacija $k$-tog reda. Ako smo na skupu s $n$ elemenata i radimo varijaciju $n$-tog reda, onda se to zove permutacija.

Kombinacija $k$-tog reda je podskup koji ima $k$ članova od nekog drugog skupa. Kombinacija je i dalje skup pa moramo članove stavljati u vitičaste zagrade. Isto tako, redoslijed više nije bitan, ali članovi se ne ponavljaju. Tako su npr. kombinacije $\{a,b,c\}$ i $\{b,a,c\}$ jednake.

Prebrojavanje

Ako imamo skup od $n$ elemenata, ukupni broj nizova duljine $k$ koje možemo napraviti je $n^k$.

Ako se elementi iz skupa ne smiju ponavljati, onda je ukupni broj takvih nizova jednak $n(n-1) \ldots(n-k+1)$.

Ukupni broj podskupova koji imaju $k$ elemenata od skupa koji ima $n$ elemenata računa se formulom:

Uvodimo oznake koje ćemo često koristiti. Prva je "n faktorijela" i označava ukupan broj permutacija na skupu od $n$ elemenata. Drugim riječima, to je broj načina na koji možemo poredati sve članove tog skupa.

Druga oznaka je za broj podskupova veličine $k$ nekog skupa koji ima $n$ elemenata. Čita se "n povrh k". Taj broj još zovemo binomni koeficijent. Lako pamtimo kao "od $n$ članova, biramo njih $k$". Povrh daje broj načina na koji to možemo napraviti. Formulu pamtimo tako da u nazivniku radimo $k$ faktorijela, a gore množimo isto toliko brojeva, od najvećeg prema manjima.

Multiskup

Multiskup je "skup" koji dopušta ponavljanje elemenata. Označavamo ih uglatim zagradama. Na primjer, za skupove znamo da je isto $\{a,b,c\}$ i $\{a,b,b,c\}$, ali za multiskupove to nije slučaj. Dakle, $[a, b, c]$ i $[a, b, b, c]$ nisu isti, ali $[a, a, b, b, c]$ i $[b, a, b, c, a]$ jesu (poredak i dalje nije bitan).

U kombinatorici se multiskup veličine $k$ zove kombinacija s ponavljanjem $k$-tog reda nad nekim skupom.

Ukupan broj multiskupova veličine $k$ nad multiskupom koji ima $n$ elemenata, odnosno broj načina kako $n$ predmeta razvrstati u $k$ podskupova računa se formulom:

Objasnimo donji primjer. Imamo 8 kuglica koje moramo podijeliti u 4 kutije. Zamislimo da prvo poredamo kuglice jednu iza druge, a zatim stavljamo štapiće između njih, prije prve kuglice ili poslije zadnje. Stavljamo 3 štapića manje - za jedan manje nego što je kutija. Razlog je taj što gledamo da su sve kuglice lijevo od prvog štapića u prvoj kutiji, kuglice između prvog i drugog štapića u drugoj kutiji, itd., a sve iza zadnjeg štapića je u zadnjoj kutiji, što je kod nas četvrta kutija.

Sve skupa imamo 11 mjesta na koje stavljamo ili kuglice ili štapiće. Mi biramo 3 mjesta na koje ćemo postaviti štapiće (ili 8 na koje ćemo staviti kuglice, isto je) i tako dobijemo broj načina na koji možemo raspodijeliti 8 kuglica u 4 kutije.

Iz tog razloga se ova metoda i zove kuglice i štapići. :)