Sbírka matematických úloh

Počet triangulací

Úloha číslo: 3429

• Nápověda

  Zafixujte jeden z trojúhelníků, ostatní k němu přidávejte.

• Řešení

  Každá taková triangulace obsahuje $n-2$ trojúhelníků, tedy existují právě dva vrcholy, do nichž nevede žádná tětiva. Zvolme jeden takový vrchol $u$ – to lze $n$ způsoby a nakresleme tento trojůhelník tak, aby $u$ byl nahoře. Nyní budeme přidávat $n-4$ trojúhelníků. U každého si můžeme zvolit jednu ze dvou možností a to zdali společná hrana byla na cestě vedoucí z vrcholu $u$ doprava nebo doleva. Poslední trojúhelník tyto dvě cesty spojí. Každou konfiguraci lze získat dvěma způsoby, protože vrchol $u$ lze zvolit dvěma způsoby.

  Např. uvedené rozdělení pětiúhelníku lze získat volbou $u=2$, čili nejprve zakreslíme trojúhelník $(1{,}2,3)$, pak přilepíme $(1{,}3,5)$ na levou cestu a zakončíme $(3{,}4,5)$.

• Odpověď

  Počet triangulací je $n2^{n-5}$ pro $n\ge 4$.