Matematické Fórum

Lubik_ · 30. 01. 2008 12:19

Zdravim, ako sa riesia priklady typu:
Na papier napisem n lavych a n pravych zatvoriek. Aka je pravdepodobnost, ze dostanem spravne uzatvorkovany vyraz?
Vdaka za pomoc, L.

Kondr · 30. 01. 2008 17:17 — Editoval Kondr (01. 02. 2008 13:00)

Všech posloupností závorek je ${2n\choose n}$
Těch správných je a_n, kde
Přitom a_0=1 a
$a_n=\sum_{i=0}^{n-1}a_ia_{n-i-1}$
(přidáme-li n-tou závorku, můžeme rozdělit případy podle toho, jak dlouhý správně uzávorkovaný výraz je uvnitř.)
A teď matematickou indukcí ukážeme, že $a_n={2n\choose n}/(n+1)$ .
Ta pravděpodobnost je proto 1/(n+1).

Kondr · 01. 02. 2008 12:58

To, co jsem se pokoušel dokázat tou indukcí, je tvrzení, že počet správně uzávorkovaných výrazů je roven Catalanovu číslu.
Protože ten důkaz už ale udělala spousta lidí přede mnou, tak pošlu jen odkaz.
http://en.wikipedia.org/wiki/Catalan_number

Matematické Fórum

#1 30. 01. 2008 12:19

Pravdepodobnost

#2 30. 01. 2008 17:17 — Editoval Kondr (01. 02. 2008 13:00)

Re: Pravdepodobnost

#3 01. 02. 2008 12:58

Re: Pravdepodobnost

Zápatí