Zoran Skoda prebrojavanje za vjerojatnost

Kažemo da su dva skupa jednakobrojni ako njihove elemente možemo uzajamno pridružiti tako da svakom elementu jednog skupa pridružujemo jedan i samo jedan element drugog skupa. Tako je nekad lakše zamijeniti neki skup drugim jednakobrojnim skupom kojeg je lakše prebrojiti. Nakon svladavanja materijala na ovoj stranici, promotrite i detaljniju stranicu prebrojavanje koja je prebrojavanje za matematiku 1, s nešto formalnijim jezikom na nekim mjestima i videa po poveznicama na dnu stranice.

Uzastopno prebrojavanje. Pretpostavimo da želimo prebrojavati slogove (poredane $p$-torke) kojima je prvi član tipa $A_1$, drugi član tipa $A_2$, itd. i neka postoji $n_1$ mogućnosti za tip $A_1$, $n_2$ mogućnosti za tip $A_2$ itd. Tada postoji

$$n_1 \times n_2 \times \cdots \times n_p$$

slogova. Npr. imamo tri vrste voća, dvije vrste kolača i pet vrsta pića. Na koliko načina možemo sastaviti marendu od jedne vrste voća, jednog kolača i jednog pića ? Odgovor: $3\times 2\times 5 = 30$ tipova marendi.

Vrlo bitno je kod takvih prebrojavanja da broj mogućnosti za tip $A_2$ ne zavisi od broja mogućnosti za tip $A_1$.

Evo jedne važne varijante. Promotrimo 5 različitih simbola, recimo brojevi 1,2,3,4,5. Na koliko načina možemo poredati tih 5 različitih simbola ? Kako bismo sastavili jedan od tih poredaka (uređaja) ? Postavili bismo 5 praznih mjesta u red i na prvo mjesto bismo stavili jedan od 5 simbola. Na drugo mjesto bismo stavili jedan od preostala 4 simbola, jer je jedan simbol već potrošen i nismo dozvolili ponavljanje. Na treće mjesto jedan od preostala 3 simbola. Na 4. mjesto jedan od preostala 2 simbola i peti simbol je onaj koji ostaje. Dakle, taj poredak možemo sastaviti na 5 puta 4 puta 3 puta 2 puta 1 način, tj. na

$$5! = 5\cdot 4\cdot 3\cdot 2\cdot 1$$

način. Ovdje koristimo simbol $!$ kojeg čitamo faktorijela. $n! = n\cdot(n-1)\cdot\ldots\cdot 2\cdot 1$, pri čemu je $1! = 0! =1$ i vrijedi $(n+1)! = (n+1)\cdot n!$. Tako je $2!=2$, $3! = 3\cdot 2 = 6$, $4! = 4\cdot 3! = 4\cdot 6 = 24$, $5! = 5\cdot 4! = 5\cdot 24 = 120$, $6! = 6\cdot 5! = 6\cdot 120 = 720$ itd.

Sve moguće poretke nekog skupa nekad nazivamo i permutacijama ili premještanjima skupa (nešto drukčija definicija: permutacija je uzajamno jednoznačno preslikavanje skupa na samog sebe, to preslikavanje je kao novo premještanje poretka). Dakle, kolekcija od $n$ objekata se može ispremiještati u red na $n!$ načina.

Što ako gledamo redove (slogove) simbola gdje se simboli mogu ponavljati ? Recimo imamo $5$ simbola, “slova” $A,B,C,D,E$ i želimo sastaviti 4-slovnu riječ od njih. Npr. $AAAB$, $ABAA$, $BCAC$ su primjeri međusobno različitih riječi. Prema uzastopnom prebrojavanju, na prvo od 4 mjesta možemo staviti bilo koje od 5 slova, na drugo bilo koje od pet slova (jer ni jedno slovo nije potrošeno, ponavljanja su dozvoljena!) itd. Tako možemo sastaviti

$$5\times 5\times 5\times 5 = 625$$

“riječi” (možda i besmislenih) od 4 slova, počevši od AAAA, AAAB, AAAC, pa sve do EEEE. Vidimo da ih je zgodno poredati leksikografski (kao u rječniku) gdje se najprije gleda prvo slovo, onda drugo slovo i kad je prvo slovo različito gleda se koje dolazi prije, a koje poslije.

Slično je recimo s bacanjem igraće kocke ili novčića. Na koliko načina možemo baciti uzastopce novčić 8 puta, ako gledamo samo koja je strana novčića pala, a redoslijed ima veze ? Pa, za svako bacanje imamo 2 mogućnosti, dakle ukupno imamo

$$2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2 = 2^8 = 256$$

mogućnosti.

Biranje grupa. Promatrajmo neku skupinu objekata koje međusobno razlikujemo. Npr. promatramo grupu od 5 ljudi, Anica, Slavica, Tonkica, Dario i Mario. Želimo odabrati troje od tih petero ljudi koji će ih predstavljati na takmičenju iz pletenja. Na koliko načina to možemo napraviti ?

U ovom zadatku poredak ljudi ne čini razliku. Dakle, ako biramo dvoje nekim redoslijedom tada je taj redoslijed suvišan, on je artefakt (umjetna tvorevina). Dakle, ako biramo troje ljudi onda prvog možemo izabrati kao jednog od 5 ljudi, drugi jedan od preostala 4 čovjeka, treći jedan od prepstal 3. To bi bilo $5\times 4\times 3$ načina, ali ta tri čovjeka koja sam izabrao sam mogao izabrati i drugim redoslijedom. Redoslijeda postoji $3! = 3\times 2\times 1$. Dakle, to je viška i $5\cdot 4\cdot 3$ redova ljudi moram grupirati u $3\cdot 2\cdot 1$ poretka istih grupa. Dakle imamo

$$\left(\begin{array}{c} 5\\ 3\end{array}\right) = \frac{5\times 4\times 3}{3\times 2\times 1} = \frac{60}{6} = 10$$

grupa ljudi. Općenito ako je $m\leq n$, tada postoji

$$\left(\begin{array}{c} n\\m \end{array}\right)= \frac{n\cdot(n-1)\cdot\ldots\cdot (n-m+1)}{m\cdot(m-1)\cdot\ldots\cdot 2\cdot 1}$$

grupa od $m$ objekata izabranih iz kolekcije od $n$ različitih objekata. Primijetite da u brojniku i nazivniku imamo isti broj množitelja (faktora). Poredak u grupi nije važan i zato dijelimo. Simbol $\left( \begin{array}{c} n\\m \end{array}\right)$ čitamo $n$ izaberi $m$ ili $n$ povrh $m$ (engleski $n$ choose $m$).

Primijetimo da je izabrati 3 od 5, isto što i izdvojiti 2 preostala iz 5 (ona 2 koja nisu izabrana). Dakle vrijedi,

$$\left( \begin{array}{c} 5\\3 \end{array}\right) = \left(\begin{array}{c} 5\\ 2\end{array}\right) = \frac{5\cdot 4}{2\cdot 1} = \frac{20}{2} = 10.$$

Općenitije, ako su $m$ i $n$ prirodni brojevi ili $0$,

$$m\leq n$$

Nekad, moramo birati podgrupe u fazama. Primjer. U grupi je 10 ljudi. Od tih 10 ljudi biramo grupu od troje koja će saditi cvjetnjak, a preostalih 7 ljudi rasporedimo u podrgupu od 5 koja će čistiti dvorište i dvoje koji će ostalima pripremati hranu dok oni radi. Na koliko načina možemo izabrati grupe za ove poslove ?

Dakle, najprije izaberemo 7 od 10 na jedan od $\left( \begin{array}{c} 10\\3 \end{array}\right)$ načina, a onda za bilo koji takav izbor izaberemo dvoje od $7$ koji će kuhati na jedan od $\left( \begin{array}{c} 7\\2 \end{array}\right)$, preostalih $5$ ljudi će onda čistiti (tu su sad svi izabrani, 5 od 5, tj na jedan način). Dakle, ukupno imamo

$$\left( \begin{array}{c} 10\\3 \end{array}\right)\cdot \left( \begin{array}{c} 7\\2 \end{array}\right) = \frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}\cdot\frac{7\cdot 6}{2\cdot 1} = \frac{720}{6}\cdot\frac{42}{2} = 120\cdot 21 = 2520$$

načina.

Vidi po želji također i stranicu prebrojavanje koja je pisana na dosta apstraktnijem nivou, i opširnija je. Ova stranica vezana je uz kolegije zadarmatstat i zadarodgoj vjstat

Preporučam i slijedeće 4 jednosatne lekcije o prebrojavanju (na hrvatskome) druge autorice, na youtubeu

yt:kP9ywSs_kVA (načela prebrojavanja)

yt:J1LOw5DmkhI (broj mogućih premještanja/permutacija)

yt:pWq2OlvjElo (varijacije)

yt:WebkCxiEX7g (kombinacije)