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:

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

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:
Catalan number binary tree example.png
  • 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:
Catalan number 4x4 grid example.svg
  • C_n 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 n=4 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]