Izvorni kôd stranice Catalanov broj

'''Catalanovi brojevi''' predstavljaju niz [[Prirodni brojevi|prirodnih brojeva]] važnih u [[Kombinatorika|kombinatorici]]. Prvih nekoliko Catalanovih brojeva jesu 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190.. Nazvani su u čast belgijskog matematičara [[Eugène Charles Catalan|Eugènea Charlesa Catalana]].

==Definicija==
Definišu se preko [[Binomni koeficijent|binomnih koeficijenata]]:

<math>C_n = 	\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!n!} =  \prod_{k=2}^n \frac{n+k}{k}  </math> za <math>n\ge 0</math>

Alternativni izraz je:

<math>C_n= \binom{2n}{n}-\binom{2n}{n+1}</math> za <math>n\ge 0</math>

== Rekurzija ==
Catalanovi brojevi zadovoljavaju rekurziju:
:<math>C_0 = 1 , C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}</math> за <math>n\ge 0</math>
Kako je <math>\tbinom{2n}{n} = \sum_{i=0}^n \tbinom{n}{i}^2,</math> tada je:
:<math>C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2.</math>.
Zadovoljavaju i sljedeću rekurziju
:<math>C_0 = 1 , C_{n+1}=\frac{2(2n+1)}{n+2}C_n,</math>

==Osobine==
Generirajuća funkcija Catalanovih brojeva je:
: <math>\sum_{n=0}^{\infty} C_n z^n = \frac{1-\sqrt{1-4 z}}{2 z}.</math>

Asimptotska vrijednost je:
:<math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.</math>

== Vanjski linkovi ==
* [http://mathworld.wolfram.com/CatalanNumber.html Catalanovi brojevi]

[[Kategorija:Cjelobrojni nizovi]]
[[Kategorija:Teme o faktorijelima i binomima]]
[[Kategorija:Enumerativna kombinatorika]]