Matematické Fórum

nordec · 01. 04. 2010 22:37

Prosím o vysvětlení pár nejasností. Vím, že počet triangulací n-úhelníku je $C_{n-2}$ , $C_n$ je Catalanovo číslo.

Ale toto mě nějak uniká:
1) Proč je to právě $C_{n-2}$ (a ne třeba $C_{n-1}$ nebo $C_{n-3}$ ), jak a z čeho to lze odvodit?
2) Pro n=2 (z definice je n, v tomto případě, nejméně 2) vychází 1 triangulace, ale jak může mít 2-úhelník triangulaci?

Za jakékoli nápady děkuji.

petrkovar · 02. 04. 2010 15:36

↑ nordec:Vztah platí pro $n\geq3$ .
Vztah se nejlépe "uvidí" z rekurzívní definice Catalánových čísel $C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$ .
V daném $(n+1)$ -úhelníku můžeme sestrojit $n-1$ různých trojúhelníků obsahujících jeden vybraný vrchol a nějakou obvodovou hranu. Pro každou volbu nesousední hrany pak můžeme zbylé dvě části (pokud existují) triangulovat nezávisle $C_k$ a $C_{n-k}$ způsoby.

nordec · 02. 04. 2010 22:40

Je pravda, že trojúhelníků bude vždy n-2 (také to vyplývá z Eulerova vzorce V+S=2+E, kde počet vrcholů je V, stěn S, hran E - těch je v triangulaci 2n-3). Ale

petrkovar napsal(a):
V daném $(n+1)$ -úhelníku můžeme sestrojit $n-1$ různých trojúhelníků obsahujících jeden vybraný vrchol a nějakou obvodovou hranu.

například v 6-úhelníku s vrcholy pospojovanými objeden (je to také triangulace) je trojúhelník neobsahující žádnou obvodovou hranu. Jak to?

petrkovar · 05. 04. 2010 14:07

↑ nordec:Ano, ale návod na cestu ke Catalanovým číslům říká něco jiného.
Není pravda, že každý trojúhelník dané triangulace obsahuje obvodovou hranu. Pravda je, že když si jeden vrchol zvolíme pevně, tak najdeme tolik a tolik trojúhelníků obsahujících tento vybraný vrchol a nějakou obvodovou hranu. Není řečeno, že je najdeme SOUČASNĚ v jedné triangulaci. Naopak, ke každému takovému trojúelníku můžeme sestavovat triangulace menších $x$ -úhelníků. A tak se pěkně odvodí rekurentní vztah pro Catalanova čísla.

nordec · 08. 04. 2010 16:19

↑ petrkovar:Tak takhle je to. Už chápu, proč to tak je. Děkuju za vysvětlení.

Matematické Fórum

#1 01. 04. 2010 22:37

Počet triangulací n-úhelníku

#2 02. 04. 2010 15:36

Re: Počet triangulací n-úhelníku

#3 02. 04. 2010 22:40

Re: Počet triangulací n-úhelníku

petrkovar napsal(a):

#4 05. 04. 2010 14:07

Re: Počet triangulací n-úhelníku

#5 08. 04. 2010 16:19

Re: Počet triangulací n-úhelníku

Zápatí