Kombinatoryka - prostokąt

tolerancja · Post autor: **tolerancja** » 17 paź 2010, o 23:06

Linie równoległe do boków prostokąta dzielą jego boki odpowiednio na k i l części. Iloma drogami, idąc bokami lub tymi liniami w prawo lub w górę, można przejśc od lewego dolnego wierzchołka do prawego górnego?

pawels · Post autor: **pawels** » 17 paź 2010, o 23:28

odpowiedź to \(\displaystyle{ {k+l\choose k}\)- musimy podjąć \(\displaystyle{ k+l}\) decyzji w którą stronę iść (po każdej przesuwamy się o jedną kratkę), ale wśród nich musi być dokładnie \(\displaystyle{ k}\) jednego typu i \(\displaystyle{ l}\) drugiego, czyli wystarczy ustalić w jakiej kolejności będziemy je podejmować, czyli wybrać k-elementowy podzbiór \(\displaystyle{ \{1,2,\ldots ,k+l\}}\).