Katalanovi brojevi

Katalanovi brojevi predstavljaju niz prirodnih brojeva značajnih u kombinatorici. Prvih nekoliko Katalanovih brojeva je: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190.. Nazvani su u čast belgijskoga matematičara Ežena Šarla Katalana.

Definicija

Mogu se definisati preko binomnih koeficijenata:

$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{ za }}n\geq 0.$

Alternativan izraz je:

$C_{n}={2n \choose n}-{2n \choose n+1}\quad {\text{ za }}n\geq 0,$

Rekurzija

Katalanovi brojevi zadovoljavaju rekurziju:

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

Pošto je ${\tbinom {2n}{n}}=\sum _{i=0}^{n}{\tbinom {n}{i}}^{2},$ onda je:

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

Zadovoljavaju i sledeću rekurziju:

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

Svojstva

Generirajuća funkcija Katalanovih brojeva je:

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

Asimptotska vrednost je:

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

Kombinatorika

Postoje mnogi problemi u kombinatorici, čije rešenje su upravo Katalanovi brojevi. Npr. konveksni poligon sa n + 2 strane da se raseći upravo na $C_{n}$ trouglova. Na slici je prikazan primer za slučaj n = 4:

Potpuno binarno stablo, gde svaki verteks ima ili dvoje dece ili je bez dece, može da predstavlja primer za Katalanove brojeve. Katalanovi broj $C_{n}$ je broj potpunih binarnih stabala sa n + 1 listom.

Literatura

• Katalanovi brojevi
• Koshy, Thomas , Catalan Numbers with Applications. . Oxford University Press. 2008. ISBN 978-0-19-533454-8.