Katalāna skaitļi

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

Kombinatorikā Katalāna skaitļi veido naturālu skaitļu virkni, kas sastopama dažādās skaitīšanas problēmās, bieži ietverot rekursīvi definētus objektus. Tie nosaukti par godu beļģu matemātiķim Eiženam Šarlam Katalānam (Eugène Charles Catalan, 1814–1894).

n-to Katalāna skaitli var izteikt tieši, izmantojot binomiālos koeficientus:

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{pie }n\ge 0.

Pirmie Katalāna skaitļi pie n = 0, 1, 2, 3, ... ir

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

Īpašības[labot šo sadaļu | labot pirmkodu]

Katalāna skaitļus Cn var aprēķināt arī pēc citas formulas:

C_n = {2n\choose n} - {2n\choose n+1} \quad\text{ ja }n\ge 0,

kas ir ekvivalenti augstākminētai formulai, jo \tbinom{2n}{n+1}=\tfrac{n}{n+1}\tbinom{2n}n. Tas parāda, ka Cn ir vesels skaitlis, kas nav acīmredzams no pirmās dotās formulas.

Katalāna skaitļiem izpildās rekurenta sakarība

C_0 = 1 \quad \mbox{un} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{pie }n\ge 0;

vēl vairāk,

C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2.

Tas ir tāpēc, ka \tbinom{2n}{n} = \sum_{i=0}^n \tbinom{n}{i}^2, jo izvēloties n skaitļus no kopas ar 2n skaitļiem var vienā vienīgā veidā sadalīt 2 daļās: izvēloties i skaitļus no pirmiem n skaitļiem un tad izvēloties n-i skaitļus no atlikušajiem n skaitļiem.

Tie arī apmierina sakarības:

C_0 = 1 \quad \mbox{un} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

kas var būt efektīvāks veids, kā tos izrēķināt.

Asimptotiski Katalāna skaitļi aug kā

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

Skatīt arī[labot šo sadaļu | labot pirmkodu]