Liczba dróg monotonicznych - liczby Catalana

[alaicja]

Pewnie wiecie , że n-ta liczba Catalana opisuje liczbę możliwych dróg monotonicznych w kwadracie \(\displaystyle{ n \times n}\), czyli takich które nie przecinają przekątnej i poruszamy sie tylko w prawo lub w górę. Jeżeli utożsamimy sobie te drogi z ciągami \(\displaystyle{ 1}\) i \(\displaystyle{ -1}\), gdzie \(\displaystyle{ 1}\) to "krok" w prawo, a \(\displaystyle{ -1}\) w górę, to ciągi te muszą spełniać warunki:
\(\displaystyle{ \sum_{i=1}^{2n} a_i =0}\), oraz
\(\displaystyle{ \sum_{i=1}^{k} a_i \ge 0, \text{ dla każdego } k =\lbrace 1, \dots , 2n\rbrace}\).
Wiem, że w ogóle wszystkich dróg (również takich które przekraczają przekątna) jest \(\displaystyle{ {2n \choose n}}\). Od tego trzeba odjąć te które powyższych warunków nie spełniają, czyli \(\displaystyle{ {2n \choose n+1}}\).

Moje pytanie brzmi jak udowodnić to, że tych "złych" dróg jest właśnie \(\displaystyle{ {2n \choose n+1}}\) ?

[Hydra147]

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2013/12/31/Drogi_w_kratach_i_kino/

.
Interesujący Cię problem to zadanie 3. dla \(\displaystyle{ n=k}\).

[alaicja]

Rzeczywiście tak, mnie jednak interesuje przykład konkretnie z ciagami Ale udało mi się wymyślić, że od momentu pojawienia się pierwszej \(\displaystyle{ -1}\) więcej, jest kilka możliwych dróg (ciągów) złych, a mianowicie:
\(\displaystyle{ {2n-1 \choose n-1}+{2n-3 \choose n-2}+{2n-5 \choose n-3}+ ... +{2n-(2n-1) \choose 0}= {2n \choose n-1}}\)
Po sprawdzeniu kilku przykładów dla małych \(\displaystyle{ n}\) rzeczywiście się zgadza, tylko jak to rozpisać i udowodnić dla dowolnego \(\displaystyle{ n}\) i się nie pomylić