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.
Iné projekty
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