Catalanovo število
Catalanova števila ali tudi Segnerjeva števila v matematiki tvorijo zaporedje naravnih števil, ki se pojavlja v mnogih preštevalnih in velikokrat rekurzivnih problemih v kombinatoriki. n-to Catalanovo število je določeno neposredno z binomskimi koeficienti:
Prva Catalanova števila za n ≥ 0 so (OEIS A000108):
Vsa Catalanova števila so naravna, saj velja:
V Pascalovem aritmetičnem trikotniku binomskih koeficientov:
n 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 9 1 9 36 84 126 126 84 36 9 1 10 1 10 45 120 210 252 210 120 45 10 1
sredinski koeficienti tvorijo zaporedje:
- 1, 2, 6, 20, 70, 252, 924, 3432, 128, 48620. ...[1]
Vsakega lahko zaporedoma delimo s celim številom 1, 2, 3, 4, ... in tako dobimo Catalanovo celoštevilsko zaporedje.
Uporabe v kombinatoriki
urediV 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:
Zatorej C3 = 5. Če si zamislimo X kot odprti oklepaj in Y kot zaprti, je vsaka Dyckova beseda dolžine 2n izraz 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«.
- 2 × 2, C1 = 1
- 3 × 3, C2 = 2
- 4 × 4, C3 = 5
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:
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.
- n = 1, C1 = 1
- n = 2, C2 = 2
- n = 3, C3 = 5
- n = 4, C4 = 14
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.
- n = 1, C1 = 1 (trivialna rešitev)
- n = 2, C2 = 2
- n = 3, C3 = 5
- n = 4, C4 = 14
Č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 S nevtralni element za zaporedja z enim elementom. Permutacija w elementov {1,...,n} je razvrstljiva po kopici, če S(w) = (1,...,n). Število permutacij {1,...,n} razvrstljivih po kopici je enako Cn.
Rekurenčna in asimptotična enačba
urediZa Catalanova števila velja rekurenčna enačba
To izhaja iz dejstva, da lahko vsako Dyckovo besedo w dolžine ≥ 2 enolično zapišemo v obliki
- w = Xw1Yw2
z (verjetno praznimi) Dyckovimi besedami w1 in w2.
Rodovna funkcija za Catalanova števila je določena z:
Z uporabo zgornje rekurenčne enačbe vidimo, da:
in zato:
Catalanova števila naraščajo asimptotsko kot:
v takšnem smislu, da količnik n-tega Catalanovega števila in izraz na desni težita k 1 za n → ∞.
Hankelova matrika
urediDeterminanta n × n Hankelove 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
urediCatalanovo 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(α).
Glej tudi
urediSklici in opombe
urediViri
uredi- Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers. New York: Copernicus. str. 96–106.
- Larcombe, P. J. (1999). »The 18th century Chinese discovery of the Catalan numbers«. Mathematical Spectrum. Zv. 32. str. 5–7. ISBN 0-387-97993-X.