Cześć.
Udowodnić, że liczba sposobów rozmieszczeń \(\displaystyle{ 2n}\) różnych liczb w tablicy o \(\displaystyle{ n}\) kolumnach i 2 wierszach tak, by w każdym wierszu i w każdej kolumnie liczby były ustawione malejąco (idąc od góry i od lewej) jest równa \(\displaystyle{ n-}\)tej liczbie Catalana.
Malejące ciągi liczb w tablicy, Catalan
-
kosa248
- Użytkownik
- Posty: 23
- Rejestracja: 20 sie 2011, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 2 razy
Malejące ciągi liczb w tablicy, Catalan
Zakładam, że wiesz, że n-ta liczba Catalana to ilość "legalnych" ciągów 2n nawiasów; legalnych czyli takich, które zaczynają się od \(\displaystyle{ (}\) i w żadnym miejscu ilość nawiasów zamykających od ilości otwierających nie jest większa, czyli jeśli np. ciąg zaczyna się od \(\displaystyle{ ()}\), to kolejny nawias musi być otwierający. No i oczywiście nawiasów otwierających jest tyle samo, co zamykających.
Wyobraź sobie, że masz nie \(\displaystyle{ n}\) kolumn, tylko \(\displaystyle{ 2n}\), ale ustawiasz liczby w ten sposób, że w każdej kolumnie jest tylko jedna oraz w każdym wierszu jest jednakowa ilość. Czyli masz ułożonych \(\displaystyle{ 2n}\) liczb w kolejności malejącej:
\(\displaystyle{ a_{2n}, a_{2n-1}, a_{2n-2}, ..., a_{2}, a_{1}}\)
Wybierasz spośród nich \(\displaystyle{ n}\) liczb i przesuwasz do dołu, tworząc dwa ciągi malejące, np.:
\(\displaystyle{ a_{2n} a_{2n-1}}\)..........\(\displaystyle{ a_{2n-3}...}\)..........(...)...\(\displaystyle{ a_{2}}\)..........
.............\(\displaystyle{ a_{2n-2}}\).............\(\displaystyle{ a_{2n-4}}\)..(...).............\(\displaystyle{ a_{1}}\)
Teraz "idziemy" od lewej strony i patrzymy, w którym wierszu występują kolejne liczby: jeśli w górnym, to stawiamy nawias otwierający, a jeśli w dolnym, to zamykający. Powstaje w ten sposób ciąg nawiasów.
Zauważ, że jeśli usuniemy luki w obu wierszach, przesuwając każdą liczbę o odpowiednią ilość miejsc w lewo, otrzymamy \(\displaystyle{ 2n}\) liczb w tablicy o \(\displaystyle{ n}\) kolumnach i 2 wierszach. W każdym wierszu dostaniemy ciąg malejący, jednak aby każda kolumna była malejąca, w naszym wyjściowym układzie, sprzed przesunięcia liczb w lewą stronę, nie może się zdarzyć sytuacja, że do pewnego miejsca ilość liczb w dolnym wierszu jest większa od ilości liczb w górnym wierszu. Przekładając to na ciąg nawiasów, nie może zdarzyć się tak, że do pewnego miejsca liczba nawiasów zamykających jest większa od liczby nawiasów otwierających, zatem nasz ciąg nawiasów musi być "legalny", a takich ciągów jest tyle, ile wynosi n-ta liczba Catalana.
Wyobraź sobie, że masz nie \(\displaystyle{ n}\) kolumn, tylko \(\displaystyle{ 2n}\), ale ustawiasz liczby w ten sposób, że w każdej kolumnie jest tylko jedna oraz w każdym wierszu jest jednakowa ilość. Czyli masz ułożonych \(\displaystyle{ 2n}\) liczb w kolejności malejącej:
\(\displaystyle{ a_{2n}, a_{2n-1}, a_{2n-2}, ..., a_{2}, a_{1}}\)
Wybierasz spośród nich \(\displaystyle{ n}\) liczb i przesuwasz do dołu, tworząc dwa ciągi malejące, np.:
\(\displaystyle{ a_{2n} a_{2n-1}}\)..........\(\displaystyle{ a_{2n-3}...}\)..........(...)...\(\displaystyle{ a_{2}}\)..........
.............\(\displaystyle{ a_{2n-2}}\).............\(\displaystyle{ a_{2n-4}}\)..(...).............\(\displaystyle{ a_{1}}\)
Teraz "idziemy" od lewej strony i patrzymy, w którym wierszu występują kolejne liczby: jeśli w górnym, to stawiamy nawias otwierający, a jeśli w dolnym, to zamykający. Powstaje w ten sposób ciąg nawiasów.
Zauważ, że jeśli usuniemy luki w obu wierszach, przesuwając każdą liczbę o odpowiednią ilość miejsc w lewo, otrzymamy \(\displaystyle{ 2n}\) liczb w tablicy o \(\displaystyle{ n}\) kolumnach i 2 wierszach. W każdym wierszu dostaniemy ciąg malejący, jednak aby każda kolumna była malejąca, w naszym wyjściowym układzie, sprzed przesunięcia liczb w lewą stronę, nie może się zdarzyć sytuacja, że do pewnego miejsca ilość liczb w dolnym wierszu jest większa od ilości liczb w górnym wierszu. Przekładając to na ciąg nawiasów, nie może zdarzyć się tak, że do pewnego miejsca liczba nawiasów zamykających jest większa od liczby nawiasów otwierających, zatem nasz ciąg nawiasów musi być "legalny", a takich ciągów jest tyle, ile wynosi n-ta liczba Catalana.