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:

Začiatok nekonečnej postupnosti Catalanových čísel (počínajúc hodnotou pre ) 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:

  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  sú všetky uzátvorkovania:
 ((()))     ()(())     ()()()     (())()     (()()). 
Ich počet (5) súhlasí s hodnotou Catalanovho čísla pre .

 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 , že žiaden jeho prefix nemá viac písmen Y, ako písmen X. Pre  sú všetky možnosti:
 XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

  je počet všetkých úplných uzátvorkovaní výrazu s  prvkami (alebo počet poradí použitia binárneho operátora na tieto prvky). Pre  máme tieto možnosti:

 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  je teda počet všetkých úplných binárnych stromov s  listami. Situácia pre  je znázornená na nasledujúcom obrázku:

center

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

  je počet všetkých monotónnych ciest na štvorcovej mriežke rozmerov  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  je znázornená na nasledujúcom obrázku:
450px|center

  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  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