Matematické Fórum

Comrad · 20. 04. 2016 19:57 — Editoval Comrad (20. 04. 2016 19:58)

Ahoj vsem! Mam problemy s timto ukolem :

Turistická cesta je lomená čára z bodu (0, 0) do bodu (2n, 0) sestávající z 2n úseček, kde každá úsečka je určena vektorem (1, 1) nebo (1, −1).
Tedy n úseček směřuje šikmo nahoru a zbylých n šikmo dolů, ale mohou být za sebou v libovolném pořadí.
Ukažte, že počet turistických cest, které nikdy neklesnou pod osu x, je stejný jako počet turistických cest, na nichž přesně jedna úsečka má pravý konec pod osou x.

Dekuji!

byk7 · 20. 04. 2016 20:03

↑ Comrad:

To plyne přímo z refurentní definice Catalánových čísel.
$C_n=\sum_{k=0}^{n-1}C_k C_{n-k-1}$

Comrad · 20. 04. 2016 20:06

↑ byk7:Diky za vzorecek, ale jak presne to plyne? Jak to souvisi s ulohou? Dekuji!

byk7 · 20. 04. 2016 20:19

↑ Comrad:

$C_n$ je počet cest, které nepodlezou osu $x$ .

Uvažme cesty, které klesnou pouze v bodě (2k,0) (přesněji mezi (2k,0) a (2k+1,0) cesta klesá, mezi (2k+1,0) a (2k+2,0) roste) – cest, které mezi (0,0) a (2k,0) osu nepodlezou, je přesně $C_{k}$ a podobně cest, které mezi (2k+2,0) a (2n,0) osu nepodlezou je $C_{n-k-1}$ .

Tedy, cest, které podlezájí osu mezi (2k,0) a (2k+2,0) je přesně $C_kC_{n-k-1}$ . Teď už to jen sečíst přes všechna $k$ .