Počet triangulací

Úloha číslo: 3429

Kolik existuje různých rozdělení pravidelného \(n\)-úhelníku na vrcholech \(1,…,n\) na trojúhelníky, tak že řezy vedou podél tětiv, které se vzájemně nekříží a navíc každý trojúhelník má alespoň jednu stranu společnou s \(n\)-úhelníkem?.

Např. pětiúhelník lze rozdělit na tři trojúhleníky \((1{,}2,3)\), \((1{,}3,5)\) a \((3{,}4,5)\).

(Rozdělení na trojúhelníky se nazývá triangulace, i když obecně není požadováno, aby každý trojúhelník měl stranu společnou s původním mnohoúhelníkem.)

  • 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\).

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