Školjka

%V0 U ovom predavanju bavit ćemo se brojanjem koliko ima objekata nekog tipa, ili na koliko načina neke objekte možemo poredati u niz. Prvo je najjednostavnije pitanje - ako imamo $n$ različitih štapića, na koliko ih različitih načina možemo poredati u niz. Ako odaberemo koji će nam štapić biti prvi (što možemo napraviti na $n$ različitih načina) dolazimo do istog problema s $n-1$ štapićem, vidimo da će ukupno rješenje biti $n \cdot$ [i]broj načina da poredamo $n-1$ štapić[/i]. Ponovnom primjenom iste logike, možemo odabrati koji će nam biti drugi štapić po redu na $n-1$ načina, pa je sada pitanje na koliko načina možemo poredati njih $n-2$, a ukupni rezultat će biti $n \cdot (n-1) \cdot $ [i]broj načina da se poreda $n-2$ štapića[/i]. Jasno je da daljnjim ponavljanjem istoga dolazimo do toga da je traženi broj načina $n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot$ [i]broj načina da poredamo $1$ štapić[/i]. Ali broj načina da poredamo $1$ štapić u niz je očito $1$. Dakle, broj načina da poredamo $n$ štapića u niz je $n \cdot (n-1) \cdot ... \cdot 2 \cdot 1$. Taj broj označavamo oznakom $n!$, a izgovaramo $n$ [b]faktorijela[/b]. Drugo je pitanje, ako imamo $n$ međusobno različitih kuglica, na koliko načina možemo odabrati njih $k$ (u ovom nam slučaju redoslijed odabira nije važan). Prvu kuglicu možemo odabrati na $n$ načina, drugu na $n-1$ načina, i tako dalje, $k$-tu možemo odabrati na $n-k+1$ načina. Dakle, ukupan broj načina je $n \cdot (n-1) \cdot ... \cdot (n-k+1)$. No rekli smo da je redoslijed odabira nevažan, pa zato sada još trebamo odrediti koliko smo puta svaki od tih skupova kuglica odabrali. To možemo odrediti tako da izračunamo na koliko načina tih $k$ kuglica možemo posložiti u niz. Gore otkrili da taj broj iznosi $k!$. Dakle, ukupan broj načina za odabrati $k$ kuglica od njih $n$ je $\dfrac{n\cdot (n-1) \cdot ... \cdot (n-k+1)}{k!}$ No, kako je to neuredno zapisivati, proširimo cijeli razlomak s $(n-k)!$ i tako dobivamo $\dfrac{n!}{(n-k)!k!}$ Ovaj broj označavamo s $\displaystyle n \choose k$, a izgovaramo $n$ [b]povrh[/b] k. Oznaka $\displaystyle n \choose k$ je poznata i pod nazivom [b]binomni koeficijent[/b].