Triangulace n-úhelníku
Úloha číslo: 3702
Kolik existuje různých triangulací pravidelného \(n\)-úhelníku s označenými vrcholy?
Řešení
Označme vrcholy cyklicky \(A_1,A_2, \ldots, A_n\) a uvažme v triangulaci trojúhelník obsahující hranu \(A_1A_2\). Nechť je jeho třetí vrchol \(A_k\), \(k \in \{3,\ldots,n\}\). Počet možných triangulací obsahujících trojúhelník \(A_1,A_2,A_k\) je pak roven \(t_{k-1}t_{n-(k-2)}\) (triangulace \((k-1)\)-úhelníku \(A_2,A_3,\ldots,A_k\) a \(n-(k-2)\)-úhelníku \(A_1,A_k,\ldots,A_n\)),
kde bereme \(t_2=1\). Platí tedy
\(\displaystyle t_n=\sum_{k=3}^n t_{k-1}t_{n-(k-2)} = \sum_{k=2}^{n-1} t_k t_{n+1-k}. \)
Pro lepší přehlednost přepíšeme bez sumy
\( t_n=t_2t_{n-1}+t_3t_{n-2}+\ldots+t_{n-2}t_3+t_{n-1}t_2\)
neboli
\(t_{n+2}=t_2t_{n+1}+t_3t_n+\ldots+t_nt_3+t_{n+1}t_2\)
Po substituci \(t_n'=t_{n+2}\)
\(t_n'=t_0't_{n-1}'+t_1't_{n-2}'+\ldots+t_{n-2}'t_1'+t_{n-1}'t_0'\)
je vidět, že dostáváme stejnou rekurenci jako pro Catalanova čísla \(b_n\) včetně stejných počátečních podmínek, tedy \(t_n=t_{n-2}'=b_{n-2}\).
Odpověď
Daný \(n\)-úhelník lze triangulovat \(\frac{1}{n-1}\binom{2n-4}{n-2}\) různými způsoby.