Počet uzávorkování

Úloha číslo: 3431

Kolik existuje různých správných uspořádání \(n\) párů závorek tak, že závorky lze správně spárovat (dobré uzávorkování)?

  • Nápověda

    Zkuste popsat každé (i špatné) uzávorkování jako cestu ve mřížce \(n\times n\) a pak hledejte vlastnost těch špatných, která vám je pomůže spočítat.

  • Řešení

    Uzávorkování s \(n\) páry závorek reprezentujeme jako cestu délky \(2n\) v mřížce \(n\times n\) (t.j. s \(n^2\) čtverci), z levého horního rohu do pravého dolního, kde závorka ( označuje krok vpravo a závorka ) krok dolů. Takových cest, tedy i všech uzávorkování je \(\binom{2n}{n}\)

    Špatná uzávorkování jsou ta, která klesnou pod diagonálu – v tom okamžiku počet použitých pravých uzavíracích závorek ) přesáhne počet levých otevíracích závorek (.

    Pro určení počtu špatných cest provedeme následující. Špatnou cestu \(P\) rozdělíme na dva úseky, a to úsek \(A\) od startu do okamžiku, kdy cesta klesla pod diagonálu a zbývající úsek \(B\). Úsek \(A\) zrcadlově převrátíme, čímž vznikne úsek \(A'\) a jeho prodloužením o \(B\) vznikne cesta \(P'\).

    Tato cesta \(P'\) je v mřížce \((n-1)\times (n+1)\). Vztah \(P \leftrightarrow P'\) je bijekce mezi špatnými cestami v původní mřížce a všemi cestami v nové mřížce, protože i u cesty \(P'\) lze určit jednoznačně rozdělení na úseky \(A'\) a \(B\). Úsek \(A'\) končí, jakmile cesta vyjde vpravo od diagonální čáry vedoucí z levého horního rohu nové mřížky. Takový okamžik musí vždy nastat, protože nová mřížka je širší než delší.

  • Odpověď

    Hledaných uzávorkování je \(\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}\).

Obtížnost: Obtížná úloha
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze