Na ile sposobów można ułożyć wiżę składającą się z \(\displaystyle{ n}\) kloców niebieskich i \(\displaystyle{ n}\) żołtych tak, aby na żadnej wysokości liczba klocków żółtych nie przewyższała liczby klocków niebieskich?
Wiem, że rozwiązaniem ma być \(\displaystyle{ \frac{1}{n + 1} \times {2n\choose n}\).
Ale jak zinterpretować ten wynik? Czy jest jakiś schemat na zadania tego typu?
Ułożenie wieży z n klocków żółtych i n niebieskich
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Ułożenie wieży z n klocków żółtych i n niebieskich
To są liczby Catalana. Poszukaj w internecie.
To co opisujesz z budowaniem wieży można zinterpretować jako liczbę dróg z punktu \(\displaystyle{ (0, 0)}\) do \(\displaystyle{ (n, n)}\) w układzie współrzędnych, nie przekraczających pól na przekątnej (tzw. dróg monotonicznych), jest to jedna z interpretacji tych liczb - dołożenie klocka niebieskiego to przejście z \(\displaystyle{ (x ,y)}\) do \(\displaystyle{ (x + 1, y)}\), a żółtego z \(\displaystyle{ (x ,y)}\) do \(\displaystyle{ (x, y + 1)}\). Liczba takich dróg jest równa liczbom Catalana.
To co opisujesz z budowaniem wieży można zinterpretować jako liczbę dróg z punktu \(\displaystyle{ (0, 0)}\) do \(\displaystyle{ (n, n)}\) w układzie współrzędnych, nie przekraczających pól na przekątnej (tzw. dróg monotonicznych), jest to jedna z interpretacji tych liczb - dołożenie klocka niebieskiego to przejście z \(\displaystyle{ (x ,y)}\) do \(\displaystyle{ (x + 1, y)}\), a żółtego z \(\displaystyle{ (x ,y)}\) do \(\displaystyle{ (x, y + 1)}\). Liczba takich dróg jest równa liczbom Catalana.