Ile jest najkrótszych dróg w kratce? Kombinacje i ścieżki na siatce

Krok 1. Droga jako ciąg kroków. Każda najkrótsza droga z $A$ do $B$ składa się z $6$ kroków w prawo (P) i $4$ kroków w górę (G) - razem $10$ kroków. Droga z rysunku to ciąg PGPPGPGGPP. Różne drogi to różne ciągi.

Krok 2. Ciąg wyznacza wybór miejsc. Ciąg jest ustalony, gdy wiemy, na których z $10$ miejsc stoją litery G (na pozostałych stoją P). Wybieramy więc $4$ miejsca z $10$, a kolejność wybierania nie gra roli - to kombinacja:

$$\binom{10}{4} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210.$$

Krok 3. Drogi przez $C$. Droga przez $C$ to droga z $A$ do $C$, a potem z $C$ do $B$. Z $A$ do $C$ robimy $3$ kroki P i $2$ kroki G, z $C$ do $B$ - też $3$ kroki P i $2$ kroki G:

$$\binom{5}{2} = 10 \quad \text{oraz} \quad \binom{5}{2} = 10.$$

Każdą pierwszą część można połączyć z każdą drugą, więc z reguły mnożenia:

$$10 \cdot 10 = 100.$$

Krok 4. Drogi omijające $C$ - dopełnienie. Od wszystkich dróg odejmujemy te przez $C$:

$$210 - 100 = 110.$$

Odpowiedź. a) $210$ dróg; b) $100$ dróg przez $C$; c) $110$ dróg omijających $C$.