Liczby Catalana - liczba monotonicznych dróg

szymonides · Post autor: **szymonides** » 31 sty 2016, o 23:48

Cześć!
Mam problem ze zrozumieniem wzoru na liczby Catalana w przypadku gdy reprezentują one ilość monotonicznych dróg rosnących (wiki:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Liczby_Catalana#Liczba_monotonicznych_dr.C3.B3g

).

Rozpisałem sobie wszystko do \(\displaystyle{ c_{4}}\), ale nadal tego nie widzę Może dlatego, że jest już późno.
Może ktoś mi wyjaśnić skąd bierze się ten wzór?

Z góry dzięki!

Kartezjusz · Post autor: **Kartezjusz** » 31 sty 2016, o 23:54

Z rekurencji. Wybierz punkt kratowy na przekątnej

szymonides · Post autor: **szymonides** » 1 lut 2016, o 00:03

Okej. Dla \(\displaystyle{ c_{4}}\) mam 3 punkty i 4 pary wywołań:
\(\displaystyle{ c_{4} = c_{0}c_{3} + c_{1}c_{2} + c_{2}c_{1} + c_{3}c_{0}}\)

W jaki sposób przyporządkować te wywołania do punktów kratowych?

Kartezjusz · Post autor: **Kartezjusz** » 1 lut 2016, o 11:34

Podziel drogę na dwie: Do punktu i od punktu