Dzień dobry,
mam problem z pewnym zadaniem o treści:
Triangulacją \(\displaystyle{ n}\)-kąta wypukłego nazywamy jego podział na \(\displaystyle{ n - 2}\) rozłączne trójkąty, których boki są bokami wielokąta lub pewnymi jego (nieprzecinającymi się) przekątnymi.
a) Ile jest wszystkich triangulacji \(\displaystyle{ n}\)-kąta wypukłego?
b) Ile spośród nich jest takich, że każdy trójkąt ma przynajmniej jeden bok będący bokiem wielokąta?
Podpunkt a) rozwiązałem - wynika on bezpośrednio z wzoru na \(\displaystyle{ n}\)-tą liczbę Catalana, czyli \(\displaystyle{ C_{n} = \frac{1}{n+1} {2n \choose n} }\).
Nie wiem natomiast jak rozwiązać podpunkt b). Proszę o pomoc.
Pozdrawiam
Liczby Catalana a triangulacja
-
f33tl0v3r
- Użytkownik
- Posty: 11
- Rejestracja: 12 lut 2020, o 19:44
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 2 razy
Liczby Catalana a triangulacja
Ostatnio zmieniony 22 gru 2020, o 00:00 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Liczby Catalana a triangulacja
Wsk:
Zauważ, że w każdym \(\displaystyle{ 2n}\) - kącie możesz narysować dwa \(\displaystyle{ n}\)-kąty takie, u których , żaden bok nie będzie bokiem \(\displaystyle{ 2n}\) kąta, czyli ich boki będą utworzone z przekątnych \(\displaystyle{ 2n}\) - kąta, a dla nieparzystych:
\(\displaystyle{ 2n+1}\) będzie tych \(\displaystyle{ n}\) - kątów: \(\displaystyle{ 2n+1}\)
Np dla:
6 kąta będzie dwa trójkąty a dla 7 kąta będzie siedem trójkątów..., itd...
Z oczywistych względów takiego nie da się zrobić w pięciokącie i poniżej...
Potem sobie odejmuj...
Dodano po 3 minutach 2 sekundach:
Więc teraz łatwo odrzucić przypadki gdzie w każdym podziale wystąpią trójkąty, których żaden z boków nie będzie bokiem bazowego\(\displaystyle{ n}\) kąta...
Dodano po 1 dniu 22 godzinach 24 minutach 36 sekundach:
Zadanie z punktu b jest to ciekawe , ciekawy przypadek trzeba było się nad tym pochylić...
Dosyć pokrętną drogą do tego doszedłem , zacząłem zliczać te rozkłady gdzie w rozkładzie jest przynajmniej jeden trójkąt nie mający boków wspólnych z wyjściowym wielokątem...
(Nie polecam nikomu tego typu rozumowania bo jest to dydaktyczne dno)...
No to zaczynajmy:
Ustalmy:
\(\displaystyle{ a_{n}}\) - ilość triangulacji wszystkich dla \(\displaystyle{ n}\) - kąta
\(\displaystyle{ b_{n}}\) - ilość triangulacji w których występuje przynajmniej jeden trójkąt, który nie ma wspólnych boków z wielokątem...
\(\displaystyle{ r_{n}}\) - szukana ilość gdzie każdy trójkąt ma przynajmniej jeden bok wspólny z wielokąta bokiem
Oczywiście:
\(\displaystyle{ r_{n}=a_{n}-b_{n}}\)
łatwo zauważyć, że dla:
Trójkąta, czworokąta, i pięciokąta mamy:
\(\displaystyle{ r_{n}=a_{n}}\)
Bo.: \(\displaystyle{ b_{n}=0}\)
Zaczniemy liczyć dla sześciokąta, zauważmy, że jedynymi trójkątami w sześciokącie które nie mają boków wspólnych z sześciokątem:
(nazwijmy takie trójkąty, trójkątami typu zero).
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}}\)
są:
\(\displaystyle{ P_{1}P_{3}P_{5} \wedge P_{2}P_{4}P_{6}}\) - trójkąty typu zero
Więc rozkładów z trójkątami typu zero będzie:
\(\displaystyle{ 1+1=2}\)
Biorąc pod uwagę, że:
\(\displaystyle{ a_{n}=c_{n-2}=14}\)
Otrzymamy:
\(\displaystyle{ r_{6}=14-2=12}\)
Weźmy dla siedmiokąta:
W siedmiokącie największą figurą , która nie ma boków wspólnych z siedmiokątem jest dalej trójkąt
siedmiokąt:
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}}\)
Trójkąty typu:
\(\displaystyle{ P_{1}P_{3}P_{5}}\) typu zero , ale będzie ich siedem
Każdy taki trójkąt tylko z jednego swego boku ma czworokąt, który ma dwa rozkłady (triangulacje)
w związku z tym:
\(\displaystyle{ r_{7}=a_{7}-b_{7}=c_{5}-2 \cdot 7=42-14=28}\)
Dla ośmiokąta, największym wielokątem nie mającym z nim punktów wspólnych będzie kwadrat:
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}P_{8}}\)
Kwadrat:
\(\displaystyle{ P_{1}P_{3}P_{5}P_{7}}\)
Lub:
\(\displaystyle{ P_{2}P_{4}P_{6}P_{8}}\)
Każdy taki kwadrat ma po dwie triangulacje, co z kwadratem daje razem cztery możliwości...
A teraz takie przypadki, że w triangulacji jest tylko jeden trójkąt typu zero (wyżej były dwa trójkąty typu zero)
1. Trójkąty typu:
\(\displaystyle{ P_{1}P_{3}P_{5}}\) - jest ich osiem
Po stronie dwóch boków tego trójkąta są trójkąty a więc mamy triangulację trywialną, a po jednej stronie tego trójkąta mamy pięciokąt:
\(\displaystyle{ P_{5}P_{6}P_{7}P_{8}P_{1}}\) w tym pięciokącie odrzucamy tylko jedną triangulację z trójkątem:
\(\displaystyle{ P_{5}P_{7}P_{1}}\) bo by się dublowało. A więc mamy możliwości:
\(\displaystyle{ 8 \cdot (5-1)=32}\)
zostają trójkąty typu: (jest ich osiem)
\(\displaystyle{ P_{1}P_{4}P_{6}}\) - po dwóch stronach tego trójkąta są czworokąty a po jednej trójkąt co da nam:
\(\displaystyle{ 8 \cdot 2 \cdot 2=32}\)
Sumując otrzymamy:
\(\displaystyle{ r_{8}=a_{8}-b_{8}=c_{6}-(32+32+4)=132-68=64}\)
Itd...
Teraz wypisałem sobie wartości naszego ciągu i wyszedł taki ciąg:
dla: \(\displaystyle{ n \ge 3, n=3,4,5,6,7,8,...}\)
\(\displaystyle{ r_{n}=1,2,5,12,28,64,...}\)
zauważmy, że:
\(\displaystyle{ r_{5}= 5=5 \cdot 2^0}\)
\(\displaystyle{ r_{6}=12=6 \cdot 2=6 \cdot 2^1}\)
\(\displaystyle{ r_{7}=28=7 \cdot 2^2}\)
\(\displaystyle{ r_{8}= 64=8 \cdot 2^3}\)
i będzie:
\(\displaystyle{ r_{9}=9 \cdot 2^4=144}\)
co da nam ogólny wzór:
\(\displaystyle{ r_{n}=n \cdot 2^{n-5}}\)
Teraz można się pobawić z dowodem indukcyjnym, zostawiam to jako ćwiczenie...
zauważmy jeszcze , że:
\(\displaystyle{ r_{4}= 4 \cdot 2^{-1}=2}\)
ale dla.:\(\displaystyle{ n=3}\) już ten wzór się nie nadaje...
więc można zapisać, że:
\(\displaystyle{ r_{n}=n \cdot 2^{n-5} , n>3}\)
dla.: \(\displaystyle{ n=3 }\)
\(\displaystyle{ r_{3}=1}\) - wyjątek...
Zauważ, że w każdym \(\displaystyle{ 2n}\) - kącie możesz narysować dwa \(\displaystyle{ n}\)-kąty takie, u których , żaden bok nie będzie bokiem \(\displaystyle{ 2n}\) kąta, czyli ich boki będą utworzone z przekątnych \(\displaystyle{ 2n}\) - kąta, a dla nieparzystych:
\(\displaystyle{ 2n+1}\) będzie tych \(\displaystyle{ n}\) - kątów: \(\displaystyle{ 2n+1}\)
Np dla:
6 kąta będzie dwa trójkąty a dla 7 kąta będzie siedem trójkątów..., itd...
Z oczywistych względów takiego nie da się zrobić w pięciokącie i poniżej...
Potem sobie odejmuj...
Dodano po 3 minutach 2 sekundach:
Więc teraz łatwo odrzucić przypadki gdzie w każdym podziale wystąpią trójkąty, których żaden z boków nie będzie bokiem bazowego\(\displaystyle{ n}\) kąta...
Dodano po 1 dniu 22 godzinach 24 minutach 36 sekundach:
Zadanie z punktu b jest to ciekawe , ciekawy przypadek trzeba było się nad tym pochylić...
Dosyć pokrętną drogą do tego doszedłem , zacząłem zliczać te rozkłady gdzie w rozkładzie jest przynajmniej jeden trójkąt nie mający boków wspólnych z wyjściowym wielokątem...
(Nie polecam nikomu tego typu rozumowania bo jest to dydaktyczne dno)...
No to zaczynajmy:
Ustalmy:
\(\displaystyle{ a_{n}}\) - ilość triangulacji wszystkich dla \(\displaystyle{ n}\) - kąta
\(\displaystyle{ b_{n}}\) - ilość triangulacji w których występuje przynajmniej jeden trójkąt, który nie ma wspólnych boków z wielokątem...
\(\displaystyle{ r_{n}}\) - szukana ilość gdzie każdy trójkąt ma przynajmniej jeden bok wspólny z wielokąta bokiem
Oczywiście:
\(\displaystyle{ r_{n}=a_{n}-b_{n}}\)
łatwo zauważyć, że dla:
Trójkąta, czworokąta, i pięciokąta mamy:
\(\displaystyle{ r_{n}=a_{n}}\)
Bo.: \(\displaystyle{ b_{n}=0}\)
Zaczniemy liczyć dla sześciokąta, zauważmy, że jedynymi trójkątami w sześciokącie które nie mają boków wspólnych z sześciokątem:
(nazwijmy takie trójkąty, trójkątami typu zero).
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}}\)
są:
\(\displaystyle{ P_{1}P_{3}P_{5} \wedge P_{2}P_{4}P_{6}}\) - trójkąty typu zero
Więc rozkładów z trójkątami typu zero będzie:
\(\displaystyle{ 1+1=2}\)
Biorąc pod uwagę, że:
\(\displaystyle{ a_{n}=c_{n-2}=14}\)
Otrzymamy:
\(\displaystyle{ r_{6}=14-2=12}\)
Weźmy dla siedmiokąta:
W siedmiokącie największą figurą , która nie ma boków wspólnych z siedmiokątem jest dalej trójkąt
siedmiokąt:
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}}\)
Trójkąty typu:
\(\displaystyle{ P_{1}P_{3}P_{5}}\) typu zero , ale będzie ich siedem
Każdy taki trójkąt tylko z jednego swego boku ma czworokąt, który ma dwa rozkłady (triangulacje)
w związku z tym:
\(\displaystyle{ r_{7}=a_{7}-b_{7}=c_{5}-2 \cdot 7=42-14=28}\)
Dla ośmiokąta, największym wielokątem nie mającym z nim punktów wspólnych będzie kwadrat:
\(\displaystyle{ P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}P_{8}}\)
Kwadrat:
\(\displaystyle{ P_{1}P_{3}P_{5}P_{7}}\)
Lub:
\(\displaystyle{ P_{2}P_{4}P_{6}P_{8}}\)
Każdy taki kwadrat ma po dwie triangulacje, co z kwadratem daje razem cztery możliwości...
A teraz takie przypadki, że w triangulacji jest tylko jeden trójkąt typu zero (wyżej były dwa trójkąty typu zero)
1. Trójkąty typu:
\(\displaystyle{ P_{1}P_{3}P_{5}}\) - jest ich osiem
Po stronie dwóch boków tego trójkąta są trójkąty a więc mamy triangulację trywialną, a po jednej stronie tego trójkąta mamy pięciokąt:
\(\displaystyle{ P_{5}P_{6}P_{7}P_{8}P_{1}}\) w tym pięciokącie odrzucamy tylko jedną triangulację z trójkątem:
\(\displaystyle{ P_{5}P_{7}P_{1}}\) bo by się dublowało. A więc mamy możliwości:
\(\displaystyle{ 8 \cdot (5-1)=32}\)
zostają trójkąty typu: (jest ich osiem)
\(\displaystyle{ P_{1}P_{4}P_{6}}\) - po dwóch stronach tego trójkąta są czworokąty a po jednej trójkąt co da nam:
\(\displaystyle{ 8 \cdot 2 \cdot 2=32}\)
Sumując otrzymamy:
\(\displaystyle{ r_{8}=a_{8}-b_{8}=c_{6}-(32+32+4)=132-68=64}\)
Itd...
Teraz wypisałem sobie wartości naszego ciągu i wyszedł taki ciąg:
dla: \(\displaystyle{ n \ge 3, n=3,4,5,6,7,8,...}\)
\(\displaystyle{ r_{n}=1,2,5,12,28,64,...}\)
zauważmy, że:
\(\displaystyle{ r_{5}= 5=5 \cdot 2^0}\)
\(\displaystyle{ r_{6}=12=6 \cdot 2=6 \cdot 2^1}\)
\(\displaystyle{ r_{7}=28=7 \cdot 2^2}\)
\(\displaystyle{ r_{8}= 64=8 \cdot 2^3}\)
i będzie:
\(\displaystyle{ r_{9}=9 \cdot 2^4=144}\)
co da nam ogólny wzór:
\(\displaystyle{ r_{n}=n \cdot 2^{n-5}}\)
Teraz można się pobawić z dowodem indukcyjnym, zostawiam to jako ćwiczenie...
zauważmy jeszcze , że:
\(\displaystyle{ r_{4}= 4 \cdot 2^{-1}=2}\)
ale dla.:\(\displaystyle{ n=3}\) już ten wzór się nie nadaje...
więc można zapisać, że:
\(\displaystyle{ r_{n}=n \cdot 2^{n-5} , n>3}\)
dla.: \(\displaystyle{ n=3 }\)
\(\displaystyle{ r_{3}=1}\) - wyjątek...