Catalanovo číslo

**Catalanove čísla**, pomenované po belgickom matematikovi Eugèneovi Charlesovi Catalanovi, sú postupnosť prirodzených čísel, ktoré sa objavujú ako riešenie viacerých kombinatorických problémov, najmä tých rekurzívneho charakteru. Definujú sa pomocou binomických koeficientov, *n*-té Catalanovo číslo je definované ako:

:C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\textrm{ pre }\ n\geq 0.

Začiatok nekonečnej postupnosti Catalanových čísel (počínajúc hodnotou pre n = 0) je:

:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

## Príklady aplikácií

Niekoľko príkladov kombinatorických problémov, kde ako riešenia figurujú Catalanove čísla:

* C_n je počet všetkých dobrých uzátvorkovaní algebraického výrazu obsahujúceho *n* párov zátvoriek (jedného druhu). Napríklad pre n=3 sú všetky uzátvorkovania:
 ((())) &nbsp;&nbsp;&nbsp; ()(()) &nbsp;&nbsp;&nbsp; ()()() &nbsp;&nbsp;&nbsp; (())() &nbsp;&nbsp;&nbsp; (()()). 
:Ich počet (5) súhlasí s hodnotou Catalanovho čísla pre n=3.

* Ak v predchádzajúcom prípade zameníme ( za X a ) za Y, dostaneme počet Dyckových slov dĺžky *2n*. Dyckove slovo je také slovo nad abecedou \Sigma = \{X,Y\}, že žiaden jeho prefix nemá viac písmen Y, ako písmen X. Pre n=3 sú všetky možnosti:
 XXXYYY &nbsp;&nbsp;&nbsp; XYXXYY &nbsp;&nbsp;&nbsp; XYXYXY &nbsp;&nbsp;&nbsp; XXYYXY &nbsp;&nbsp;&nbsp; XXYXYY.

* C_n je počet všetkých úplných uzátvorkovaní výrazu s n+1 prvkami (alebo počet poradí použitia binárneho operátora na tieto prvky). Pre n=3 máme tieto možnosti:
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))

* Uzátvorkovanie, čiže postupnosť použití binárneho operátora, z predchádzajúceho príkladu sa dá reprezentovať pomocou úplného (každý uzol má buď dvoch synov alebo žiadneho syna) binárneho stromu. Číslo C_n je teda počet všetkých úplných binárnych stromov s n+1 listami. Situácia pre n=3 je znázornená na nasledujúcom obrázku:

center

* C_n je počet všetkých neizomorfných pestovaných (s daným koreňom a usporiadaním poradia potomkov daného uzla) stromov.

* C_n je počet všetkých monotónnych ciest na štvorcovej mriežke rozmerov n \times n takých, že nepretínajú hlavnú diagonálu. Monotónna cesta je taká cesta, ktorá začína v ľavom dolnom rohu, končí v pravom hornom rohu a pozostáva len z hrán orientovaných vpravo alebo hore. Enumerácia takýchto ciest je ekvivalentná s problémom Dyckových slov, pričom X reprezentuje posun doprava a Y reprezentuje posun hore. Situácia pre n=4 je znázornená na nasledujúcom obrázku:
450px|center

* C_n je počet všetkých možností, ako je možné rozdeliť pravidelný *(n+2)*-uholník na trojuholníky iba pridaním úsečiek medzi vrcholmi daného *(n+2)*-uholníka. Všetky možnosti pre prípad n=4 sú znázornené na nasledujúcom obrázku:
400px|center

Kombinatorických problémov, kde vystupujú Catalanove čísla, je omnoho viac. Matematik Richard Peter Stanley ich vo svojej knihe *Enumerative Combinatorics: Volume 2* zozbieral až 66.

## Externé odkazy

* Stanley, Richard Peter: Catalan addendum to Enumerative Combinatorics, Volume 2 
* Catalanove čísla - MathWorld 
* Príklady problémov, v ktorých sa vyskytujú Catalanove čísla 
* Kalkulačka na Catalanove čísla  pre *n* až 200000 
* Catalanove čísla 

Kategória:Postupnosti čísel
Kategória:Kombinatorika