Zoran Skoda prebrojavanje

Neki principi prebrojavanja. Vidi također elementarniju stranicu prebrojavanje za vjerojatnost gdje možete naći dodatne primjere, slučajeve i objašnjenja.

Po definiciji, kardinalitet (brojnost) skupova je ista, tj. znamo da skup $A$ ima $n$ elemenata ako postoji uzajamno jednoznačno preslikavanje, tj. bijekcija $f:A\to B$. Dakle ako $A$ ima $n$ elemenata, tada skup $B$ ima također $n$ elemenata. Vidi stranicu ekvipotentni skupovi. Za uniju dvaju skupova kažemo da je disjunktna ako razlikujemo elemente prvog od elemenata drugog skupa, tj. da je njihov presjek prazan skup. Brojnost disjunktne unije je zbroj brojnosti oba skupa.

Ako presjek dva skupa nije prazan, tada je brojnost unije dan formulom

$$kard(A\cup B) = \kard(A)+kard(B)-kard(A\cap B)$$

jer smo elemente u presjeku $A\cap B$ brojili dva puta.

Brojnost Kartezijevog produkta skupova je umnožak njihovih brojnosti. Npr. $kard(A\times B\times C) = kard(A)\cdot kard(B)\cdot kard(C)$.

Kod brojanja različitih skupova sastavljenih od elemenata danih skupova, njihovih $n$-torki i slično uvijek treba imati na umu da li se ti elementi mogu više puta pojavljivati kao različite “kombinacije” ili ne, te da li je bitan njihov redoslijed ili ne.

Permutacije bez ponavljanja i s ponavljanjem

Npr. neka je riječ neka kombinacija slova. Redoslijed slova je bitan, dakle gledamo uređene petorke slova bez ponavljanja. Koliko ima riječi duljine 5 koje su sastavljene od slova $A,B,C,D$ i $E$ tako da se ni jedno slovo ne ponovi ? Primjeri takvih riječi su npr. $ABCDE$ i $BACDE$ ali nije $AACBB$. Na prvo mjesto možemo staviti jedno od $5$ danih slova, na drugo jedno od $4$ preostala slova, na treće jedno od preostala $3$ itd. Dakle, postoji $5\cdot 4\cdot 3\cdot 2\cdot 1 = 5! = 120$ takvih riječi. Općenito definiramo $0! = 1$, $1! = 1$, te rekurzivno $(n+1)! = (n+1)\cdot n!$, dakle $n! = n(n-1)(n-2)\cdots 2\cdot 1$ za $n\geq 1$. Izraz $n!$ čitamo en faktorijela. Faktorijela je dakle rekurzivno definirana funkcija sa skupa $\mathbf{N}_0$ u skup $\mathbf{N}$.

Koliko ima riječi od 5 slova kod kojih je dozvoljeno i ponavljanje, npr. $AABBC$ ? Tada na prvo mjesto možemo staviti jedno od $5$ slova, na drugo opet $5$…dakle imamo $5\times 5\times 5\times 5\times 5 = 5^5 = 3125$ riječi. Ako je $S$ skup čiji elementi su slova $\{A,B,C,D,E\}$, tada te riječi točno odgovaraju (dakle u bijekciji su sa) skupu $S\times S\times S\times S\times S$. To je ujedno broj funkcija sa skupa $\{1,2,3,4,5\}$ u skup $S$. Zaista, takva funkcija $f$ kaže koje smo slovo stavili na $k$-to mjesto, naime $f(k)\in S$. Broj funkcija iz $\{1,2,3,4,5\}$ u $S$ je $kard(S)^5$ gdje je $5$ u eksponentu zapravo brojnost skupa $\{1,2,3,4,5\}$. Npr. riječ $DBCCD$ na prvom mjestu ima $D$, na drugom mjestu ima $B$ pa njoj odgovara funkcija $f_{DBCCD}$ za koju vrijedi $f_{DBCCD}(1) = D$, $f_{ABCCD}(2) = B$ itd.

Zadatak. Na koliko načina možemo poredati 5 ljudi u krug, ako nam je bitno samo tko je lijevo/desno od koga ?

Odgovor: na $5!/5 = 4!$ načina. Zaista, kad bi bili u liniji onda je $5!$ načina, ali ako rotiramo cijelu grupu dobijemo istu konfiguraciju sa stanovišta njihovog relatiuvnog položaja. Dakle grupe po 5 ekvivalentnih položaja čine razrede, pa ima $5!/5 = 24$ razreda. Obratno, netko može sjesti gdje hoće sve je to isto, a ostalih 4 se raspoređuju na preostala 4 mjesta, pa je $4!$ načina.

Biranje skupa dobitaka iz vreće

Promatrajmo vreću Djeda Mraza u kojoj postoji $11$ različitih paketa od čega je Djed Mraz odlučio nama dati $3$ paketa. Koliko različitih mogućnosti dobitka postoji ? Primijetimo da u takvoj situaciji ne razlikujemo dobitak u različitom redoslijedu. Kad bi redoslijed imao veze onda nam on može nekim redoslijedom dati jedan od $11$ paketa kao prvi, pa jedan od preostalih $10$ kao drugi, te jedan od preostalih $9$ kao treći, ponavljanja nema. Dakle, $11\cdot 10\cdot 9 = 990$ načina. No ti načini su u grupa od $3!$ onih koji su isti u raznom redoslijedu. Dakle, postoji

$$\frac{11\cdot 10\cdot 9}{3\cdot 2\cdot 1} = 165$$

različitih dobitaka kad redoslijed nema veze. Pišemo i

$$\frac{11\cdot 10\cdot 9}{3\cdot 2\cdot 1} = \frac{11\cdot 10\cdot 9\cdot 8!}{3\cdot 2\cdot 1\cdot 8!} = \frac{11!}{3!8!} = \left(\array{11\\ 3}\right)$$

različitih dobitaka.

Zamislimo sad da Djed Mraz zapravo ima $11$ tipova paketa, a da u vreći postoji i više paketa od svake vrste tako da možemo dobiti i tri ista paketa ako treba. U tom slučaju imamo ponavljanje pa je problem puno teži. Kad bi redoslijed bio bitan, imali bi smo $11\times 11\times 11 = 1331$ dobitaka s različitim redoslijedom, no ne možemo taj broj podijeliti s $3!$ da dobijemo dobitke bez redoslijeda. Naima, $ABC$ ima $3! = 6$ varijanti u odnosu na redoslijed, no $AAA$ ima samo jednu varijantu jer u svakom redoslijedu izgleda isto, pa nisu sve kombinacije u grupama od $6$. Ovakav primjer dakle moramo podijeliti na podslučajeve, tako da u svakom podslučaju situacija bude jasna.

Prvi podslučaj: sva tri paketa različita, to već znamo: $11$ povrh $3$, tj. $165$ dobitaka.

Drugi podslučaj: dva paketa ista, jedan od neke druge vrste. Izaberemo na $11$ načina paket kojeg dobijemo dva puta, i na $10$ načina kojeg imamo $1$ put. Dakle, $110$ različitih dobitaka.

Treći podslučaj: sva tri paketa ista. Postoji $11$ dobitaka sa samo jednim tipom paketa.

Dakle, postoji ukupno $165+110+11 = 286$ različitih dobitaka.

Dijeljenje u grupe neodređene veličine

Neka je $S$ skup, a $A,B,C,\ldots$ disjunktni podskupovi takvi da je $A\cup B\cup C\cup\ldots = S$. Kažemo da određivanje takvih podskupova čija disjunktna unija je $S$ čini particiju skupa $S$. U tom terminu zapravo nije jasno da li su prazni skupovi dozvoljeni ili nisu.

Koliko ima particija konačnog skupa $S$ od $n$ elemenata na $k$ disjunktnih podskupova, pri čemu neki od njih mogu biti i prazni i pri čemu razlikujemo redoslijed tih podskupova ? Za svaki element nam je bitno u kojem je od $k$ skupova i ništa više. Dakle taj skup je u bijekciji sa skupom funkcija iz skupa $\{1,2,\ldots,k\}$ u $S$, dakle $n^k$.

Zamislimo sad drugu krajnost, da imamo neke predmete iste vrste, npr. bijele kuglice i dijelimo u $k$ kutija (redoslijed kutija bitan). Te raspodjele se mogu predočiti kao da smo u niz posložili $n$ bijelih kuglica i stavili $(k-1)$-pregradu između njih. Bijele kuglice između $r-1$-ve i $r$-te pregrade su sadržaj $r$-te kutije. Dakle, imamo $n+k-1$ predmeta u nizu (kako kuglice tako i pregrade) i moramo izabrati koji od tih predmeta su u stvafri pregrade. To dakle daje broj $\left(\array{n+k-1\\ k-1}\right)$.

Zamislimo sad imamo $5$ bijelih, $3$ crne i $2$ crvene kuglice i stavljamo ih u 4 kutije. Dakle, $k-1 = 4 - 1 = 3$. Bijele kuglice rasporedimo na $\left(\array{5+3\\ 3}\right)= 56$ načina (npr. raspored $\circ \circ \circ | | \circ |\circ$, tj. $3 . 0 .1 .1$ kuglica ili $|\circ\circ\circ\circ | \circ|$ tj. raspored od redom $0.4.1.0$ kuglica), crne kuglice na $\left(\array{3+3\\ 3}\right) = 20$ načina i crvene na $\left(\array{2+3\\ 3}\right) = 10$ načina. Ukupno dakle sve kuglice na $56 \cdot 20\cdot 10 = 11200$ načina raspoređujemo na tri kutije pri čemu kutije razlikujemo, a kuglice iste boje ne razlikujemo.

Binomni razvoj

Binomni teorem. Neka je $n$ pozitivan cijeli broj i $x,y$ brojevi. Tada vrijedi binomna formula

$$(x + y)^n = \sum_{i = 1}^n \left(\array{n\\ i}\right) x^i y^{n-i} = \sum_{i = 1}^n \frac{n!}{i!(n-i)!} x^i y^{n-i} = \sum_{i = 1}^n \sum_{j =1}^{n-i} \frac{n!}{i!j!} x^i y^j.$$

Koeficijenti u binomnoj formuli su jedan redak u Pascalovom trokutu. Pascalov trokut je simetričan (npr. koeficijenti u jednom od redaka su $1, 4, 6, 4, 1$). To je zapravo identitet

$$\left(\array{n\\ k}\right) = \left(\array{n\\ n-k}\right).$$

To je vrlo korisno. Npr.

$$\left(\array{8\\ 6}\right) = \left(\array{8\\ 2}\right) = \frac{8\cdot 7}{2\cdot 1} = 4\cdot 7 = 28.$$

Binomna formula se dokazuje matematičkom indukcijom, no možemo razmišljati i ovako. Pomnožimo li nekoliko binoma jedan s drugim po distributivnosti moramo zbrojiti sve umnoške od po jedan pribrojnik u svakom monomu. Ako gledamo dakle

$$(x+y)\cdot (x+y)\cdots (x+y)$$

gdje ima ukupno $n$ zagrada, tada se $x^i y^{n-i}$ pojavljuje $\left(\array{ n\\ i}\right) = \frac{n!}{i!(n-i)!}$ jer na toliko načina možemo izabrati $i$ faktora u kojima smo izabrali $x$, a u drugim zagradama izaberemo $y$.

To je korisno jer to lako proširimo na potencije polinoma. Npr.

$$(x + y + z)^n = \sum_{i + j + k = n} \frac{n!}{i!j!k!} x^i y^j z^k,$$

gdje se gledaju samo nenegativni cijeli $i,j,k$. Naime, od $n$ pozicija možemo izabrati $i$ za $x$-eve na $\frac{n!}{i!(n-i)!}$ načina, a onda od preostalih $(n-i)$ pozicija možemo izabrati $y$-e na $\frac{(n-i)!}{j!(n-i-j)!}$ načina. Preostale pozicije su za $z$-ove (samo jedan način). Pomnožimo te brojeve $\frac{n!}{i!(n-i)!}\cdot\frac{(n-i)!}{j!(n-i-j)!}$, skratimo s $(n-i)!$ i dobijemo $\frac{n!}{i!j!(n-i-j)!} =\frac{n!}{i!j!k!}$, gdje je $k = n-i-j$ (ili, ekvivalentno, $i+j+k=n$).

Linkovi

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)

category: zadarmat1