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.

Obtížnost: Středně těžká úloha
Úloha vyžadující neobvyklý trik nebo nápad
Komplexní úloha
En translation
	Zaslat komentář k úloze