V knjigi Preštevalna kombinatorika: 2. del (Enumerative Combinatorics: Volume 2) Richarda Stanleyja iz leta 1999 je navedenih 66 različnih razlag Catalanovih števil. Tu je navedenih nekaj primerov.
Cn je enak številu Dyckovih besed dolžine 2n. Dyckova beseda je znakovni niz, ki vsebuje toliko n X-ov in n Y-ov, da noben njen začetni odsek nima več Y-ov kot X-ov. Na primer, Dyckove besede dolžine 6 so:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
Zatorej C3 = 5. Če si zamislimo X kot odprti oklepaj in Y kot zaprti, je vsaka Dyckova beseda dolžine 2nizraz z n pari oklepajev, pravilno postavljenih skupaj:
((())) ()(()) ()()() (())() (()())
Dyckove besede lahko naravno predstavimo kot določene monotone poti v mreži z (n + 1) × (n + 1) točkami v kartezični ravnini, povezanimi z navpičnimi in vodoravnimi črtami. Monotona pot se začne v spodnjem levem kotu v izhodišču (0,0) in se končna v zgornjem desnem kotu v točki (n, n), pri tem pa vodi zmeraj desno (1,0) ali gor (0,1) in nikoli preko diagonale: (1,1) ali (1, -1). X pomeni »korak v desno«, Y pa »korak navzgor«.
Dyckove besede lahko preštejemo z naslednjim veščim pristopom D. Andréa: osredotočimo se na tiste besede z n X-i in n Y-i, ki niso Dyckove besede. V takšni besedi najdemo prvi Y, ki krši Dyckov pogoj, in potem vse črke za Y-om preklopimo iz Y-ov v X-e in obratno. Tako dobimo besedo z n + 1 Y-i in n - 1 X-i. V bistvu lahko vsako takšno besedo dobimo po tej poti na natanko en način. Število teh besed je enako:
in je tako enako številu neDyckovih besed. Število Dyckovih besed mora potemtakem biti:
kar je n-to Catalanovo število Cn.
Cn je tudi število različnih načinov popolnih postavitev oklepajev med n + 1 faktorjev. Na primer za n = 3 imamo 5 različnih postavitev oklepajev 4 faktorjev:
a(b(cd)) a((bc)d) (ab)(cd) (a(bc))d ((ab)c)d
Takšne izraze lahko naravno predstavimo kot korenska urejena dvojiška drevesa tako, da Cn prešteva število takšnih dreves z n+1 listi.
Cn je enako tudi številu različnih načinov delitve mnogokotnika z n + 2 stranicami v trikotnike, če povežemo njegova oglišča z ravnimi črtami. Tu so mišljeni sklenjeni konveksni mnogokotniki.
Če je w končno zaporedje različnih celih števil, določimo njegovo preureditev S(w) rekurzivno: zapišemo w = unv, kjer je n največji element v w in u, v pa so krajša zaporedja. Nastavimo S(w) = S(u)S(v)n, kjer je Snevtralni element za zaporedja z enim elementom. Permutacijaw elementov {1,...,n} je razvrstljiva po kopici, če S(w) = (1,...,n). Število permutacij {1,...,n} razvrstljivih po kopici je enako Cn.
v takšnem smislu, da količnikn-tega Catalanovega števila in izraz na desni težita k 1 za n → ∞.
Hankelova matrika
Determinantan × nHankelove matrike, katere elementi (i, j) so Catalanova števila Ci+j−2, je enaka 1, ne glede na vrednost n. Za n = 5 je na primer:
Če so elementi »zamaknjeni«, da so Catalanova števila Ci+j−1, je determinanta še vedno enaka 1, ne glede na velikost n. Na primer za n = 5:
Catalanova števila tvorijo edino zaporedje s takšno značilnostjo.
Zgodovina
Catalanovo zaporedje je prvič opisal Leonhard Euler, ki se je zanimal za število različnih načinov delitve mnogokotnika v trikotnike. Belgijski matematik Eugène Charles Catalan (1814—1894) je pri raziskovanju uganke hanojskih stolpov odkril povezavo za izraze z oklepaji in se zaporedje imenuje po njem. Vešč postopek preštevanja za Dyckove besede je našel D. André leta 1887.
Leta 1988 so v kitajski publikaciji Neimenggu Daxue Xuebao objavili, da je zaporedje Catalanovih števil na Kitajskem uporabljal matematik Antu Ming od leta 1730. Tedaj je začel pisati svojo knjigo Ge Yuan Mi Lu Jie Fa, ki jo je dokončal njegov študent Chen Jixin leta 1774, vendar je bila objavljena šestdeset let kasneje. Larcombe je prikazal nekaj podrobnosti o delu Antuja Minga, vključno z vzpodbudo Pierra Jartouxa, ki je to neskončno vrsto pokazal na Kitajskem v začetku 18. stoletja.[2] Ming je rabil Catalanova števila pri razvoju vrst za sin(2α) in sin(4α) s členi sin(α).
