P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 18 (1990/1991) Številka 1 Strani 12-16
Marko Razpet:
REZANJE VECKOTNIKA NA TRIKOTNIKE
Ključne besede: matematika, geometrija.
Elektronska verzija: http://www.presek.si/18/1023-Razpet.pdf
© 1990 Društvo matematikov, fizikov in astronomov Slovenije © 2009 DMFA - založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovoljeno.
REZANJE VEČKOTNIKA NA TRIKOTNIKE
Vzemimo v ravnini poljuben izbočen ali konveksen večkotnik. Z rezanjem ga lahko razdelimo na same trikotnike na neskončno mnogo načinov. Tukaj se bomo omejili na naslednji način rezanja: Večkotnik režemo z njegovimi diagonalami, ki se ne sekajo v notranjosti. Nekoč so nam v osnovni Soli pripovedovali, da je diagonalo odkril sam Pitagora, ki je imel prekratko posteljo, po diagonali iz kota v kot pa mu je bila ravno pravšnja.
Naj ima naš večkotnik n oglišč, kjer je n > 3. Z našim načinom rezanja povežemo nekatera oglišča z diagonalami. Stranicam in diagonalam skupaj bomo rekli povezave, ker povezujejo oglišča večkotnika. Ne pozabimo, režemo na same trikotnike. Rešili bomo naslednje naloge:
1.	Izračunaj število En povezav, ki jih dobimo na ta način!
2.	Izračunaj Število Tn trikotnikov, na katere smo razrezali rt-kotnik!
3.	Poišči število Dn vseh različnih rezanj danega /»-kotnika na same trikotnike na prej opisani način!
Odgovor na prvo vprašanje je preprost. Pri trikotniku imamo 3 povezave, torej £3 — 3, pri štiri kotniku nastane pri dogovorjenem načinu rezanja 5 povezav, to se pravi = 5. Ni težko videti, da dobimo pri /1+ 1-kotniku le dve povezavi več kot pri «-kotniku, to pomeni, da velja preprosta zveza En+\ — En + 2. Iz te pa hitro najdemo formulo
En — 2n - 3 , n > 3
Podobno izračunamo Število Tn. Najprej je očitno Tj — 1 in T4 = 2. Pri dogovorjenem načinu rezanja dobimo pri n + 1-kotniku !e en trikotnik več kot pri rezanju n-kotnika, to pomeni, da velja zveza Tn+1 = Tn + 1. iz katere takoj sledi
Tn = n - 2 , n> 3
Zaradi popolnosti označimo z On število oglišč, ki nastopajo v naših nalogah. Seveda je On = n. Pri tem velja enakost
On - En + Tn = 1 , n > 3
v kateri bodo starejši bralci spoznali Eulerjev izrek.
Precej teže pa je rešiti tretjo nalogo. Za n-kotnike z majhnim številom oglišč n pridemo do Števil Dn z risanjem vseh možnosti. Za n = 3 imamo
Slika 1. Rezanje petkotnlka na trikotnike
trikotnik in tu ni kaj rezati. To pomeni D3 = 1. Za n = 4 dobimo Stirikotnik in D4 = 2. Za petkotnik dobimo že 5 možnosti (slika 1): D5 = 5,
Števila Dn za n > S bomo izračunali rekurzivno, to je z že znanimi Števili
D3j£>4, ... ,Dn-1
Mislimo si, tfa imamo /j-kotnik in v njem izbrano neko stranico, ki ji pravimo baza (slika 2). Iz krajiSČ te baze povlecimo diagonali v neko drugo ogiišče našega /i-kotnika. Naj ima večkotnik desno od trikotnika z bazo i, oni na levi strani pa j stranic, kjer je i > 3 In j > 3. Števili 1 in / nista neodvisni.
Slika 2. Trikotnik z bazo
Očitno mora veljati enakost i+j— 2 + 1 = n. torej i+j ~ /7 + 1. OgliSče trikotnika z bazo naj se sedaj spreminja po vseh tistih ogliSčih n-kotnika. ki niso krajfšča baze. Za / > 3 in j > 3 lahko dobljene /- in 7-kotnike desno in levo od trikotnika z bazo Se naprej režemo na trikotnike na D/ oziroma Dj načinov, pri tem je / > 3, / ■>3 in / +/== n +1. Pri izbranem trikotniku z bazo lahko to naredimo na D/Dj načinov. Če pa se zgodi, da je/ = n — 1. ko se desno od trikotnika z bazo večkotnik izrodi v daljico (slika 2 desno), lahko dalje delimo na trikotnike le n — 1-kotnik levo od trikotnika z bazo. in to na Dn_j načinov. Podobno je s to rečjo v primeru i = n — 1. Za n > S velja torej enakost
Dn = Dn-i + £>3£V2 + 040/1-3 + ■ - - + 0/7-2^3 + Pn~i
ki jo lahko krajSe zapišemo tudi takole:
Z zadnjo formulo lahko izračunamo Se nadaljnje člene zaporedja Dn :
Seveda nas zanima končna formula za Števila Dn. Te tu ne bomo
dokazovali, glasi pa se takole:
n-1
Dn = 2D„_1 + J2 DlDn+l-i , » > 5
1=3
Db = 14, D7 = 42, Dg = 132, Dg = 429, D10 = 1430,...
pri tem smo uporabili binomski koeficient
o katerem smo v PRESEKU že dosti pisali. Naloga: Pokaži, da iz zgornje formule sledi
An - 6
■Dn
n
Števila Dn se ne pojavljajo samo pri naSem problemu, ampak tudi drugod. Oglejmo si problem postavljanja oklepajev. Denimo.da imamo znake a, b, c, d v tem vrstnem redu. Zanima nas. na koliko načinov lahko mednje postavimo tri predkiepaje "{" i» tri zaklepaje ")" tako, da nikjer ne nastopata predkiepaj "(" in zaklepaj ")" eden za drugim, ne da bi kaj oklepala, to se pravi, izločevali bomo možnost "()". Poudarimo, da je vrstni red znakov a, b, c, d stalen. Te možnosti so:
((*)(«/)),	Mbc))d)t (a((6c)rf)), W*{erf))J
Možnosti je torej 5. to je Ds. Ali je kakšna zveza med Številom rezanja večkotnika na trikotnike in postavljanjem oklepajev na opisani način v splošnem primeru? Je. Med n znake lahko tako postavimo o - 1 predklepajev "(" in n — i zaklepajev ")" tako. da se "('' in ")" nikdar ne srečata skupaj, na D/,+ 1 načinov. To vidimo tako. Stranice n + 1-kotnika označimo z n znaki, ena pa ostane zaenkrat neoznačena. Na opisani način razrežemo /i + l-kotmk na trikotnike na vseh Dn+ j možnih načinov. Če lahko v danem primeru stranici a, b (a, b sta katerikoli stranici) zaključimo v trikotnik, označimo tretjo stranico z (afc). Prej ali slej pridemo po večkotniku naokrog in nazadnje lahko označimo tudi prvotno neoznačeno stranico večkotnika (slika 1).
(c(b(cdJ)J
Slika 3. DvoJISka drevesa s petimi Izhodi
Znan je še en primer, v katerem imamo opraviti s Števili Dn> To je primer dvojiških ali binarnih dreves. Dvojiško drevo (primerjaj ga z rodovnikom, tudi v PRESEKU je bilo o drevesih že marsikaj napisanega) ima eno točko posebej odlikovano, pravimo ji koren. Iz njega izstopata dve vejit v vsako drugo točko pa vstopa ena veja, izstopata pa dve ali nobena. Tistim točkam, v katere vstopa ena veja. izstopa pa nobena, pravimo izhodi drevesa. Dvojiška drevesa z izhodi a,/>,c,c/ v predpisanem vrstnem redu so na sliki 3. Očitno vsakemu dvojtškemu drevesu pripada neka postavitev oklepajev med znake a,b^c)d. Vsakokrat označimo točko, iz katere izhajata veji do a in b. z (a/?), če vodita veji do b in (cd), označimo izhodno točko z (¿(a/)) in tako naprej. Dvojiških dreves z n izhodi, ki so označeni v danem vrstnem redu, je natančno Dn.
VeČkotnik srno v našem primeru rezali na trikotnike. Podobno bi lahko rezali tudi na štirikotnike, petkotnike ...Lahko pa bi dovolili tudi druge možnosti: večkotnik bi rezali deloma na trikotnike, deloma na štirikotnike itd. V tem primeru bi dobili števila, ki so v tesni zvezi z onimi, ki smo jih srečali pri šahovskem kralju.
Uporabljena literatura: H. G. Forder: Some Problems in Combinatorics. The Math. Gazette 45 (1961), str. 199-201 G. Polya, R. E. Tarjan, D. R, Woods: Notes on Introductory Combinatorics, Birkhauser. Boston Basel Stuttgart 1983
P. S.: V tretji številki Preseka 16 seje v program KINGPATH prikradla napaka. Vrstica 320 se pravilno glasi : B [Y] :=0;
Marko Razpet