Catalanovo število

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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)!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ za } n\ge 0.

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

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

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).

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

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 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
Monotona pot na mreži 2 × 2
  • 3 × 3, C2 = 2
Monotoni poti na mreži 3 × 3
  • 4 × 4, C3 = 5
Monotone poti na mreži 4 × 4

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 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.

  • n = 1, C1 = 1
Dvojiško drevo z dvema listoma
  • n = 2, C2 = 2
Dvojiški drevesi s tremi listi
  • n = 3, C3 = 5
Dvojiška drevesa s štirimi listi
  • n = 4, C4 = 14
Dvojiška drevesa s petimi 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.

  • n = 1, C1 = 1 (trivialna rešitev)
    Delitev trikotnika na trikotnik
  • n = 2, C2 = 2
    Delitev štirikotnika na trikotnika
  • n = 3, C3 = 5
Delitev petkotnika na trikotnike
  • n = 4, C4 = 14
Delitev šestkotnika na trikotnike

Č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[uredi | uredi kodo]

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 = Xw1Yw2

z (verjetno praznimi) Dyckovimi besedami w1 in w2.

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 → ∞.

Hankelova matrika[uredi | uredi kodo]

Determinanta 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:

\det\begin{bmatrix}1 & 1 & 2 & 5 & 14 \\ 1 & 2 & 5 & 14 & 42 \\ 2 & 5 & 14 & 42 & 132 \\ 5 & 14 & 42 & 132 & 429 \\ 14 & 42 & 132 & 429 & 1430 \end{bmatrix} = 1 \!\, .

Č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:

\det\begin{bmatrix}1 & 2 & 5 & 14 & 42 \\ 2 & 5 & 14 & 42 & 132 \\ 5 & 14 & 42 & 132 & 429 \\ 14 & 42 & 132 & 429 & 1430 \\ 42 & 132 & 429 & 1430 & 4862 \end{bmatrix} = 1 \!\, .

Catalanova števila tvorijo edino zaporedje s takšno značilnostjo.

Zgodovina[uredi | uredi kodo]

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(α).

Glej tudi[uredi | uredi kodo]

Sklici in opombe[uredi | uredi kodo]

  1. ^ Conway, Guy (1996).
  2. ^ Larcombe (1999).

Viri[uredi | uredi kodo]