Apskatīt Katalāna skaitļi izejas kodu

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

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

:<math>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.</math>

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

:[[1 (skaitlis)|1]], 1, [[2 (skaitlis)|2]], [[5 (skaitlis)|5]], [[14 (skaitlis)|14]], [[42 (skaitlis)|42]], 132, 429, 1430, 4862, 16796, ...

== Īpašības ==
Katalāna skaitļus ''C''<sub>''n''</sub> var aprēķināt arī pēc citas formulas:
:<math>C_n = {2n\choose n} - {2n\choose n+1} \quad\text{ ja }n\ge 0,</math>
kas ir ekvivalenti augstākminētai formulai, jo <math>\tbinom{2n}{n+1}=\tfrac{n}{n+1}\tbinom{2n}n</math>. Tas parāda, ka ''C''<sub>''n''</sub> ir [[vesels skaitlis]], kas nav acīmredzams no pirmās dotās formulas.

Katalāna skaitļiem izpildās rekurenta sakarība
:<math>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;</math>
vēl vairāk,
:<math>C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2.</math>
Tas ir tāpēc, ka <math>\tbinom{2n}{n} = \sum_{i=0}^n \tbinom{n}{i}^2,</math> jo izvēloties ''n'' skaitļus no kopas ar 2''n'' 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:
:<math>C_0 = 1 \quad \mbox{un} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,</math>
kas var būt efektīvāks veids, kā tos izrēķināt.

Asimptotiski Katalāna skaitļi aug kā
:<math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}</math>.

== Skatīt arī ==
* [[Fibonači skaitļi]]

{{autoritatīvā vadība}}

[[Kategorija:Veselu skaitļu virknes]]
[[Kategorija:Kombinatorika]]