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 AA ima nn elemenata ako postoji uzajamno jednoznačno preslikavanje, tj. bijekcija f:ABf:A\to B. Dakle ako AA ima nn elemenata, tada skup BB ima također nn 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(AB)=kard(A)+kard(B)kard(AB) kard(A\cup B) = \kard(A)+kard(B)-kard(A\cap B)

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

Brojnost Kartezijevog produkta skupova je umnožak njihovih brojnosti. Npr. kard(A×B×C)=kard(A)kard(B)kard(C)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 nn-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,DA,B,C,D i EE tako da se ni jedno slovo ne ponovi ? Primjeri takvih riječi su npr. ABCDEABCDE i BACDEBACDE ali nije AACBBAACBB. Na prvo mjesto možemo staviti jedno od 55 danih slova, na drugo jedno od 44 preostala slova, na treće jedno od preostala 33 itd. Dakle, postoji 54321=5!=1205\cdot 4\cdot 3\cdot 2\cdot 1 = 5! = 120 takvih riječi. Općenito definiramo 0!=10! = 1, 1!=11! = 1, te rekurzivno (n+1)!=(n+1)n!(n+1)! = (n+1)\cdot n!, dakle n!=n(n1)(n2)21n! = n(n-1)(n-2)\cdots 2\cdot 1 za n1n\geq 1. Izraz n!n! čitamo en faktorijela. Faktorijela je dakle rekurzivno definirana funkcija sa skupa N 0\mathbf{N}_0 u skup N\mathbf{N}.

Koliko ima riječi od 5 slova kod kojih je dozvoljeno i ponavljanje, npr. AABBCAABBC ? Tada na prvo mjesto možemo staviti jedno od 55 slova, na drugo opet 55…dakle imamo 5×5×5×5×5=5 5=31255\times 5\times 5\times 5\times 5 = 5^5 = 3125 riječi. Ako je SS skup čiji elementi su slova {A,B,C,D,E}\{A,B,C,D,E\}, tada te riječi točno odgovaraju (dakle u bijekciji su sa) skupu S×S×S×S×SS\times S\times S\times S\times S. To je ujedno broj funkcija sa skupa {1,2,3,4,5}\{1,2,3,4,5\} u skup SS. Zaista, takva funkcija ff kaže koje smo slovo stavili na kk-to mjesto, naime f(k)Sf(k)\in S. Broj funkcija iz {1,2,3,4,5}\{1,2,3,4,5\} u SS je kard(S) 5kard(S)^5 gdje je 55 u eksponentu zapravo brojnost skupa {1,2,3,4,5}\{1,2,3,4,5\}. Npr. riječ DBCCDDBCCD na prvom mjestu ima DD, na drugom mjestu ima BB pa njoj odgovara funkcija f DBCCDf_{DBCCD} za koju vrijedi f DBCCD(1)=Df_{DBCCD}(1) = D, f ABCCD(2)=Bf_{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!5!/5 = 4! načina. Zaista, kad bi bili u liniji onda je 5!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=245!/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!4! načina.

Biranje skupa dobitaka iz vreće

Promatrajmo vreću Djeda Mraza u kojoj postoji 1111 različitih paketa od čega je Djed Mraz odlučio nama dati 33 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 1111 paketa kao prvi, pa jedan od preostalih 1010 kao drugi, te jedan od preostalih 99 kao treći, ponavljanja nema. Dakle, 11109=99011\cdot 10\cdot 9 = 990 načina. No ti načini su u grupa od 3!3! onih koji su isti u raznom redoslijedu. Dakle, postoji

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

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

11109321=111098!3218!=11!3!8!=(11 3) \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 1111 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×11×11=133111\times 11\times 11 = 1331 dobitaka s različitim redoslijedom, no ne možemo taj broj podijeliti s 3!3! da dobijemo dobitke bez redoslijeda. Naima, ABCABC ima 3!=63! = 6 varijanti u odnosu na redoslijed, no AAAAAA ima samo jednu varijantu jer u svakom redoslijedu izgleda isto, pa nisu sve kombinacije u grupama od 66. 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: 1111 povrh 33, tj. 165165 dobitaka.

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

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

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

Dijeljenje u grupe neodređene veličine

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

Koliko ima particija konačnog skupa SS od nn elemenata na kk 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 kk skupova i ništa više. Dakle taj skup je u bijekciji sa skupom funkcija iz skupa {1,2,,k}\{1,2,\ldots,k\} u SS, dakle n kn^k.

Zamislimo sad drugu krajnost, da imamo neke predmete iste vrste, npr. bijele kuglice i dijelimo u kk kutija (redoslijed kutija bitan). Te raspodjele se mogu predočiti kao da smo u niz posložili nn bijelih kuglica i stavili (k1)(k-1)-pregradu između njih. Bijele kuglice između r1r-1-ve i rr-te pregrade su sadržaj rr-te kutije. Dakle, imamo n+k1n+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 (n+k1 k1)\left(\array{n+k-1\\ k-1}\right).

Zamislimo sad imamo 55 bijelih, 33 crne i 22 crvene kuglice i stavljamo ih u 4 kutije. Dakle, k1=41=3k-1 = 4 - 1 = 3. Bijele kuglice rasporedimo na (5+3 3)=56\left(\array{5+3\\ 3}\right)= 56 načina (npr. raspored |||\circ \circ \circ | | \circ |\circ, tj. 3.0.1.13 . 0 .1 .1 kuglica ili ||||\circ\circ\circ\circ | \circ| tj. raspored od redom 0.4.1.00.4.1.0 kuglica), crne kuglice na (3+3 3)=20\left(\array{3+3\\ 3}\right) = 20 načina i crvene na (2+3 3)=10\left(\array{2+3\\ 3}\right) = 10 načina. Ukupno dakle sve kuglice na 562010=1120056 \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 nn pozitivan cijeli broj i x,yx,y brojevi. Tada vrijedi binomna formula

(x+y) n= i=1 n(n i)x iy ni= i=1 nn!i!(ni)!x iy ni= i=1 n j=1 nin!i!j!x iy j. (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,11, 4, 6, 4, 1). To je zapravo identitet

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

To je vrlo korisno. Npr.

(8 6)=(8 2)=8721=47=28. \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)(x+y)(x+y) (x+y)\cdot (x+y)\cdots (x+y)

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

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

(x+y+z) n= i+j+k=nn!i!j!k!x iy jz k, (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,ki,j,k. Naime, od nn pozicija možemo izabrati ii za xx-eve na n!i!(ni)!\frac{n!}{i!(n-i)!} načina, a onda od preostalih (ni)(n-i) pozicija možemo izabrati yy-e na (ni)!j!(nij)!\frac{(n-i)!}{j!(n-i-j)!} načina. Preostale pozicije su za zz-ove (samo jedan način). Pomnožimo te brojeve n!i!(ni)!(ni)!j!(nij)!\frac{n!}{i!(n-i)!}\cdot\frac{(n-i)!}{j!(n-i-j)!}, skratimo s (ni)!(n-i)! i dobijemo n!i!j!(nij)!=n!i!j!k!\frac{n!}{i!j!(n-i-j)!} =\frac{n!}{i!j!k!}, gdje je k=nijk = n-i-j (ili, ekvivalentno, i+j+k=ni+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

Last revised on June 1, 2021 at 15:58:04. See the history of this page for a list of all contributions to it.