MetaMath '22

Lijep pozdrav svima! Dobrodošli na još jedan kombinatorni tjedan. Ovaj put bavit ćemo se metodom matematičke indukcije i metodom dvostrukog prebrojavanja. Ovdje ćemo pogledati nekoliko riješenih primjera glede dvostukog prebrojavanja. Ta metoda se najčešće koristi kada želimo dokazati neki identitet $A=B$ pri čemu na oba izraza $A$ i $B$ možemo gledati na kombinatorni način (u zadacima su to često sume i produkti binomnih koeficijenata ili pak faktorijela). Rješavanje takvih zadataka možemo svesti na tri djela: \begin{enumerate} \item Određivanje skupa $S$ čije ćemo elemente prebrojiti na dva načina \item Dokazivanje da vrijedi $|S|=A$ \item Dokazivanje da vrijedi $|S|=B$ \end{enumerate} Tada princip dvostrukog prebrojavanja kaže da vrijedi $A=B$, pa smo time dokazali traženi identitet. No najprije ćemo ponoviti nekoliko definicija i kombinatorno dokazati dva korisna rezultata. Najprije, \textbf{faktorijel} prirodnog broja $n$ definira se kao produkt svih prirodnih brojeva manjih ili jednakih od broja $n$ i obično se označava sa $n!$. Dakle, $$n!=n\cdot(n-1)\cdot\ldots\cdot2\cdot1.$$ Obično još dogovorno stavljamo $0!=1.$ Neka su sada $n$ i $k$ cijeli brojevi takvi da je $0\leq k\leq n$. Definiramo $$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$ Broj $\binom{n}{k}$ nazivamo \textbf{binomni koeficijent} (drugi rješeni primjer opravdava naziv tog broja).