60% POPUSTA na instrukcije! Klikni i ostvari popust.

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.

Varijacija - mobile

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

n na k - mobileca1501373dc2fce52363639de12b1b06733aaf9enizovi s razlicitim elementima - mobile52a4d780d58b9008eee1b325c3ecebc913f37ae1

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". 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.

$ \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 $k$ nad multiskupom koji ima $n$ elemenata, 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 kuglica u 4 kutije.

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

štapici i kuglice - mobilebc5afa56d36067d20786985d61f02c8af2048b32
ONLINE INSTRUKCIJE

Instrukcije cijeli mjesec, 5 predmeta,

13 eura!

ŠTO ČEKAŠ?

Isprobaj potpuno besplatno!

Registracijom dobivaš besplatan*
pristup dijelu lekcija za svaki predmet.

*Besplatan pristup ne zahtijeva unos kartice.
Online pripreme za maturu i instrukcije za srednju školu. Dostupno 24/7.
© 2023, Gradivo.hr