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. Tako su npr. kombinacije ${a,b,c}$ i ${b,a,c}$ jednake.

Flowers

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)$.

Flowers
Flowers

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

\( \frac{n(n-1) \cdot(n-2) \cdots(n-k+1)}{1 \cdot 2 \cdot 3 \cdots k} \)

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.

\( n!=1 \cdot 2 \cdot \ldots \cdot n \)

Druga oznaka je za broj podskupova veličine $k$ nekog skupa koji ima $n$ elemenata. Čita se "n povrh k". 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.

\( \left(\begin{array}{l} n \\ k \end{array}\right)=\frac{n !}{k !(n-k) !} \)

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 $n$, odnosno broj načina kako $n$ predmeta razvrstati u $k$ podskupova računa se formulom:

\( \binom{n+k-1}{k-1} \)

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 kuglic u 4 kutije.

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

Flowers
Matematika
pripreme za maturu