Sirul lui Catalan

download Sirul lui Catalan

of 12

Transcript of Sirul lui Catalan

.

n cadrul acestui articol vom prezenta cteva informatii referitoare la celebrul sir a lui Catalan, precum si diferite probleme a cror rezolvare se bazeaz pe acest sir

Eugne Charles Catalan .S-a nascut n Bruges (acum oras Belgian)la data de 30 mai 1814 si a decedat n orasul belgian Lige la data de 14 februarie 1894.Studiaza matematica n Paris la cole Polytechnique avndu-i ca profesori favoriti pe Joseph Liouville(1809 1882) si pe Jacques Charles Franois Sturm(1803 1855).Obtine doctoratul n matematica n 1841.Studentul sau preferat a fost Ernesto Cesro(1859 1906)cu care a corespondat pe tot parcursul vietii(a trimis ntre 1890 -1894, 52 de scrisorisi a primit de la Cesro 7 raspunsuri)

Sirul numerelor lui Catalan apare frecvent n problemele de combina- toric. Acestaeste definit astfel:=Asadar, avem:

C0 = 1, C1 = 1, C2=2, C3 = 5, C4 = 14, C5 = 42, C6=132, C7=429, C8 = 1430, C9 = 4862, C10 = 16796, C11 = 58786 etc.

Problema 1:Triangularizarea unui poligon convex n cte moduri poate fi triagularizat un poligon convex cu n+2 vrfuri

4 varfuri2 modalitati

5 varfuri5 modalitatii

6 varfuri14 modalitati

Problema 2: nchiderea corect a parantezelor: cte moduri se poate scrie un sir cu n paranteze deschise i n nchise, astfel nct ele s fie nchise corect. De exemplu, (()()) este un sir corect, iar ())()( nu este un sir corect deoarece a treia parantez nu are pereche. ()()2 perechi 2 modalitti

(())

()()() ()(()) (())() (()()) ((()))

3 perechi 5 modalitti

()()()() ()()(()) ()(())() ()(()()) ()((())) (())()() (())(()) (()())() ((()))() (()()()) (()(())) (())()), ((()())) (((())))4 perechi 14 modalitti

Problema 3 Numrul arborilor binari completi: Un arbore binar complet este un arbore cu rdcin n care fiecare vrf are 0 sau 2 fii. Cti arbori binari completi cu n noduri interne exist ?

2 noduri interne 2 modalitati

3 noduri interne 5 modalitati

Problema 4 Strngeri de mn peste masa rotund: Dac 2 n persoane sunt asezate n jurul unei mese rotunde, n cte moduri pot s si dea mna simultan n perechi astfel nct s nu si ncruciseze nimeni braele peste mas?

2 perechi 2 modalitati

3 perechi 5 modalitati

4 perechi 14 modalitati

Problema 5 Votare cu problem: Presupunnd c doi candidati, Andrei si Bogdan, primesc n final fiecare cte n voturi, n cte moduri pot fi numrate acestea astfel nct Bogdan s nu fie niciodat naintea lui Andrei?

2 voturi fiecare2 modalitat

3 voturi fiecare5 modalitati

4 voturi fiecare 14 modalitati

Echivalenta problemelor n cele ce urmeaz vom enunta si vom schita demonstratia unei teoreme care arat c cele 5 probleme enuntate anterior sunt echivalente si se rezolv folosind sirul numerelor lui Catalan. Teorem Urmtoarele multimi de obiecte au acelasi numr de elemente si acest numr este Demonstraie Vom construi bijectii pentru a artac mulimile M1, M2, M3, M4,M5,M6 au acelasi numr de elemente,dup care vom arta c acest numr este

n acest caz trebuie s demonstrm c exist o bijectie dintre multimea triangularizrilor unui poligon cu n+2 vrfuri si multimea scrierilor cu paranteze a n + 1 factori. Dac poligonul are n + 2 vrfuri si acestea sunt A1, A2, ..., An+2, atunci obtinem o scriere cu paranteze a produsului x1 x2... xn deplasndu-nepe laturile poligonului pornind din A1pn la An+1

Numerotm persoanele de la mas de la 1 la 2 n succesiv. Vom construi o bijectie astfel: pornim cu persoana 1 si ne deplasm circular spre persoana 2 n, dac persoana i d mna cu persoana j si i < j atunci se adaug oparantez deschis, altfel parantez nchis.4 Prezentm n continuare modul de construire a parantezrii pentru situatia din imaginea alturat.Oricrei modalitti de salut i va corespunde o parantetizare corect si invers datorit faptului c strngerile de mn nu se "ncruciseaz" (persoanelede o parte si de cealalt a fiecrei"strngeri de mn" formeaz grupuri distincte care se salut reciproc.), lucru care se poate demonstra prin inductie si rmne ca exercitiu.