Catalanovo číslo

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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í[upraviť | upraviť zdroj]

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:
Catalan number binary tree example.png
  • 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:
Catalan number 4x4 grid example.svg
  • je počet všetkých možností, ako môžme 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:
Catalan-Hexagons-example.svg

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[upraviť | upraviť zdroj]