Numrat e Catalanit

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\geq 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ë

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.

• C_n ë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ë, C_n na jep numrin e shprehjeve të cilat përmbajnë n çifte kllapash të vendosura në mënyrë korrekte:

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

• C_n ë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:

• C_n ë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:

Lidhje të jashtme

• Stanley, Richard P. (1998), Catalan addendum to Enumerative Combinatorics, Volume 2 (PDF) {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)
• Dickau, Robert M.: Catalan numbers
• Davis, Tom: Catalan numbers.

Shih edhe

Numrat greko-latine