rekurzija?

[xxx]

Trebam pomoc.
Kako se moze na temelju putova u cjelobrojnoj mrezi dokazati rekurzija za Catalanove brojeve:Cn=C0C(n-1)+C1C(n-2)+C2C(n-3)+...+C(n-1)C(0), ali bas iz tih puteva?

[ahri]

ja to dobih kao "broj razlicitih puteva iz tocke (0,0) u (n,n) s tim da se mices po za jednu tocku "udesno" i "gore" + sto nikad ne smijes preci pravac x=y (tj. uvijek x<=y ili x>=y).

_________________

[vsego]

Davno sam se ja bavio kombinatorikom ali ovo mi zvuci blisko, pa ti mozda pomogne... http://degiorgi.math.hr/forum/viewtopic.php?t=1357

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[krcko]

OK, sad su te podsjetili na ono sto si vjerojatno zna(o/la). C(n) je jednak broju najkracih puteva od (0,0) do (n+1,n+1) koji nemaju zajednickih
tocaka s pravcem y=x (osim prve i zadnje).

Grupiras puteve prema prvoj tocki u kojoj dodiruju pravac y=x-1 (ne racunajuci (1,0), kroz koju svi prolaze). Recimo da je to (m,m+1) za prirodan broj m. Putevi se raspadaju na dva dijela: od (1,0) do (m+1,m) i od (m+1,m) do (n+1,n+1). Translatiras (1,0) u ishodiste i vidis da prvih dijelova ima C(m-1). Drugom dijelu mozes nakalemiti segmentic [(m,m),(m+1,m)], translatirati (m,m) u ishodiste i vidjeti da ih ima C(n-m). Po principu produkta spojeva prvog i drugog dijela ima C(m-1)*C(n-m). A po principu sume C(n) je zbroj toga za m=1,2,...,n.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.