Numrat e Catalanit

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko

Numrat e Catalanit janë terma të një vargu i cili shumë hpesh paraqitet si zgjidhje e shumë problemeve në kombinatorikë dhe përkufizohet në mënyrë rekurzive. Emrin e ka marrë sipas matematikanit belg Eugene Charles Catalan (1814–1894).

Numri Catalanit pra termi n të i vargut të Catalanit jepet si koeficient i binomit me formulën

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ për }n\ge 0.

Disa nga termat e para të vargut të Catalanit janë :1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, , …

Zbatimet në kombinatorikë[redakto | redakto tekstin burimor]

Libri Enumerative Combinatorics: Volume 2 i matematikanit të shquar aerikan Richard P. Stanley përmban një përmbledhje problemesh të cilat japin 66 interpretime të ndryshme të numrave të Catalanit. Në vazhdim do të paraqesim disa interpretime të rëndësishme të këtyre numrave.

  • Cn është numri i fjalëve të Dyckut të gjatësisë 2n. Fjala e Dyckut është vargu i cili si terma përmban n X'a dhe n Y'a të tillë që pjesa fillestare e vargut ka më pak Y' se X'a. Për shembull të gjitha fjalët e Dyckut të gjatësisë 6 janë:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  • Po të interpretohet symboli X as si hapje kllape ,,(,, dhe Y si mbyllje kllape ,,),, atëherë, Cn na jep numrin e shprehjeve të cilat përmbajnë n çifte kllapash të vendosura në mënyrë korrekte:
((()))     ()(())     ()()()     (())()     (()())
  • Cn është numri i rrugëve monotone në një rrjetë prej n × n katrorësh, të cilat nuk kalojnë mbi diagonale e katrorit. RRuga monotone fillon në këndin e poshtëm majtas dhe mbaron në këndin e sipërm djathtas të rrjetës katrore dhe gjatë kësaj kemi të drejtë të lëvizim djathtas ose lartë. Ç'do rrugë monotone përcakton një fjalë të Dyckut ku: X do të thotë lëvizje djathtas ndërsa Y lëvizje lartë. Më poshtë e kemi ilustruar rastin n = 4:
Catalan number 4x4 grid example.svg
  • Cn është numri i ndarjeve të poligonit konveks me n + 2 brinjë në trekëndësha duke i lidhur kulmet e tij me drejtëza (vija të drejta). Më poshtë kemi dhënë ndarjet e mundshme të gjashtë këndëshit të cilit i korrespondon rasti kur n = 4:
Pastedpic 02172009 192058.png

Lidhje të jashtme[redakto | redakto tekstin burimor]

Shih edhe[redakto | redakto tekstin burimor]

Numrat greko-latine