Catalanov broj

Catalanovi brojevi predstavljaju niz prirodnih brojeva važnih u 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ènea Charlesa Catalana.

Definicija

Definišu se preko binomnih koeficijenata:

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!n!}}=\prod _{k=2}^{n}{\frac {n+k}{k}}}$ za ${\displaystyle n\geq 0}$

Alternativni izraz je:

${\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}}$ za ${\displaystyle n\geq 0}$

Rekurzija

Catalanovi brojevi zadovoljavaju rekurziju:

${\displaystyle C_{0}=1,C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}}$ за ${\displaystyle n\geq 0}$

Kako je ${\displaystyle {\tbinom {2n}{n}}=\sum _{i=0}^{n}{\tbinom {n}{i}}^{2},}$ tada je:

${\displaystyle C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.}$.

Zadovoljavaju i sljedeću rekurziju

${\displaystyle C_{0}=1,C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}$

Osobine

Generirajuća funkcija Catalanovih brojeva je:

${\displaystyle \sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.}$

Asimptotska vrijednost je:

${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}$

Vanjski linkovi

• Catalanovi brojevi