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:

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}=\prod _{k=2}^n\frac{n+k}{k}$ za $n\ge 0$

Alternativni izraz je:

$C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})$ za $n\ge 0$

Rekurzija

Catalanovi brojevi zadovoljavaju rekurziju:

$C_0=1,C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}$ за $n\ge 0$

Kako je $(\genfrac{}{}{0ex}{}{2n}{n})=\sum _{i=0}^n{(\genfrac{}{}{0ex}{}{n}{i})}^2,$ tada je:

$C_n=\frac{1}{n+1}\sum _{i=0}^n{(\genfrac{}{}{0ex}{}{n}{i})}^2.$.

Zadovoljavaju i sljedeću rekurziju

$C_0=1,C_{n+1}=\frac{2(2n+1)}{n+2}{C}_n,$

Osobine

Generirajuća funkcija Catalanovih brojeva je:

$\sum _{n=0}^{\mathrm{\infty }}{C}_n{z}^n=\frac{1-\sqrt{1-4z}}{2z}.$

Asimptotska vrijednost je:

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

Vanjski linkovi

• Catalanovi brojevi