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.

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

n 1×n 2××n p 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×2×5=303\times 2\times 5 = 30 tipova marendi.

Vrlo bitno je kod takvih prebrojavanja da broj mogućnosti za tip A 2A_2 ne zavisi od broja mogućnosti za tip A 1A_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!=54321 5! = 5\cdot 4\cdot 3\cdot 2\cdot 1

način. Ovdje koristimo simbol !! kojeg čitamo faktorijela. n!=n(n1)21n! = n\cdot(n-1)\cdot\ldots\cdot 2\cdot 1, pri čemu je 1!=0!=11! = 0! =1 i vrijedi (n+1)!=(n+1)n!(n+1)! = (n+1)\cdot n!. Tako je 2!=22!=2, 3!=32=63! = 3\cdot 2 = 6, 4!=43!=46=244! = 4\cdot 3! = 4\cdot 6 = 24, 5!=54!=524=1205! = 5\cdot 4! = 5\cdot 24 = 120, 6!=65!=6120=7206! = 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 nn objekata se može ispremiještati u red na n!n! načina.

Što ako gledamo redove (slogove) simbola gdje se simboli mogu ponavljati ? Recimo imamo 55 simbola, “slova” A,B,C,D,EA,B,C,D,E i želimo sastaviti 4-slovnu riječ od njih. Npr. AAABAAAB, ABAAABAA, BCACBCAC 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×5×5×5=625 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

22222222=2 8=256 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×4×35\times 4\times 3 načina, ali ta tri čovjeka koja sam izabrao sam mogao izabrati i drugim redoslijedom. Redoslijeda postoji 3!=3×2×13! = 3\times 2\times 1. Dakle, to je viška i 5435\cdot 4\cdot 3 redova ljudi moram grupirati u 3213\cdot 2\cdot 1 poretka istih grupa. Dakle imamo

(5 3)=5×4×33×2×1=606=10 \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 mnm\leq n, tada postoji

(n m)=n(n1)(nm+1)m(m1)21 \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 mm objekata izabranih iz kolekcije od nn 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 (n m)\left( \begin{array}{c} n\\m \end{array}\right) čitamo nn izaberi mm ili nn povrh mm (engleski nn choose mm).

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

(5 3)=(5 2)=5421=202=10. \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 mm i nn prirodni brojevi ili 00,

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

(10 3)(7 2)=10983217621=7206422=12021=2520 \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. Ova stranica vezana je uz kolegije zadarmatstat i zadarodgoj vjstat

Created on December 14, 2018 at 06:44:21. See the history of this page for a list of all contributions to it.