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:

${\displaystyle 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 ${\displaystyle 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:

• ${\displaystyle 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 ${\displaystyle n=3}$ sú všetky uzátvorkovania:

Ich počet (5) súhlasí s hodnotou Catalanovho čísla pre ${\displaystyle 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 ${\displaystyle \Sigma =\{X,Y\}}$, že žiaden jeho prefix nemá viac písmen Y, ako písmen X. Pre ${\displaystyle n=3}$ sú všetky možnosti:

• ${\displaystyle C_{n}}$ je počet všetkých úplných uzátvorkovaní výrazu s ${\displaystyle n+1}$ prvkami (alebo počet poradí použitia binárneho operátora na tieto prvky). Pre ${\displaystyle n=3}$ máme tieto možnosti:

${\displaystyle ((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 ${\displaystyle C_{n}}$ je teda počet všetkých úplných binárnych stromov s ${\displaystyle n+1}$ listami. Situácia pre ${\displaystyle n=3}$ je znázornená na nasledujúcom obrázku:

• ${\displaystyle 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.

• ${\displaystyle C_{n}}$ je počet všetkých monotónnych ciest na štvorcovej mriežke rozmerov ${\displaystyle 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 ${\displaystyle n=4}$ je znázornená na nasledujúcom obrázku:

• ${\displaystyle 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 ${\displaystyle n=4}$ sú znázornené na nasledujúcom obrázku:

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 (po anglicky)
• Catalanove čísla - MathWorld (po anglicky)
• Príklady problémov, v ktorých sa vyskytujú Catalanove čísla (po anglicky)
• Kalkulačka na Catalanove čísla pre n až 200000 (po anglicky)
• Catalanove čísla