5. Zadatak

Od starta do cilja potrebno je 10 pomaka, od kojih je 7 pomaka desno i 3 gore. Ako se sa $D$ označi pomak za jedan udesno, a sa $G$ pomak za jedan prema gore, put od starta do cilja može se napisati kao uređena desetorka u kojoj je 7 $D$-ova i 3 $G$-a. Pitanje je koliko ima različitih desetorki s tim svojstvom.

Prvi način prebrojavanja:

Položaj prvog $G$ može se izabrati na 10 načina, drugog $G$ na preostalih 9 i trećeg $G$ na preostalih 8 načina. To je ukupno $10\cdot9\cdot8=720$ načina. Međutim, kako nije važno koji je $G$ izabran prvi, koji drugi, a koji treći, taj broj 720 treba podijeliti sa 6 jer je svaka moguća trojka ubrojena 6 puta ($3\cdot2\cdot1$).

Dakle, do cilja je ukupno 120 puteva.

Drugi način prebrojavanja:

Deset različitih slova možemo poredati na $10\cdot9\cdot8\cdot\ldots\cdot2\cdot1$ načina. S obzirom da, u našem primjeru imamo deset slova od kojih je 7 $D$-ova i 3 $G$-a, svaka permutacija tih sedam istih slova $D$ (kojih ima $7\cdot6\cdot\ldots\cdot2\cdot1$) i tri ista slova $G$ (kojih ima $3\cdot2\cdot1$) daje istu uređenu desetorku slova u kojoj je sedam slova $D$ i tri slova $G$. Zato je ukupni broj putova jednak

$$\frac{10\cdot9\cdot\ldots\cdot2\cdot1}{7\cdot6\cdot\ldots\cdot2\cdot1\cdot3\cdot2\cdot1}=120.$$