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:

((()))     ()(())     ()()()     (())()     (()()).

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     XYXXYY     XYXYXY     XXYYXY     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:

• $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:

• $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:

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 Archivované 2010-04-11 na Wayback Machine pre n až 200000 (po anglicky)
• Catalanove čísla