Catalanovo število

Iz Wikipedije, proste enciklopedije

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:

$C_n = \frac{1}{n+1} {2n\choose n} = \frac{(2n)!}{n! \; (n+1)!} \qquad\mbox{ za } n\ge 0.$

Prva Catalanova števila za n ≥ 0 so (OEIS A000108):

1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Vsa Catalanova števila so naravna, saj velja:

$C_n = {2n\choose n} - {2n\choose n-1} \qquad\mbox{ za } n\in\mathbb{N}\; (n\ge 1).$

[uredi] Uporabe v kombinatoriki

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.

C_n 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 C₃ = 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, C₁ = 1

3 × 3, C₂ = 2

4 × 4, C₃ = 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:

${2n\choose n-1}$

in je tako enako številu neDyckovih besed. Število Dyckovih besed mora potemtakem biti:

${2n\choose n}-{2n\choose n-1} \; ,$

kar je n-to Catalanovo število C_n.

C_n 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 C_n prešteva število takšnih dreves z n+1 listi.

n = 1, C₁ = 1

n = 2, C₂ = 2

n = 3, C₃ = 5

n = 4, C₄ = 14

C_n 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, C₁ = 1 (trivialna rešitev)

n = 2, C₂ = 2

n = 3, C₃ = 5

n = 4, C₄ = 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 enak 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 C_n.

[uredi] Rekurenčna in asimptotična enačba

Za Catalanova števila velja rekurenčna enačba

$C_0 = 1 \qquad \mbox{ in } \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{ za } n\ge 1$

To izhaja iz dejstva, da lahko vsako Dyckovo besedo w dolžine ≥ 2 enolično zapišemo v obliki

w = Xw₁Yw₂

z (verjetno praznimi) Dyckovimi besedami w₁ in w₂.

Rodovna funkcija za Catalanova števila je določena z:

$c(x)=\sum_{n=0}^\infty C_n x^n \; .$

Z uporabo zgornje rekurenčne enačbe vidimo, da:

$c(x)=1+xc(x)^2\,$

in zato:

$c(x) = \frac{1-\sqrt{1-4x}}{2x} \; .$

Catalanova števila naraščajo asimptotsko kot:

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

v takšnem smislu, da količnik n-tega Catalanovega števila in izraz na desni težita k 1 za n → ∞.

[uredi] 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 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.