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
[uredi | uredi izvor]Mogu se definisati preko binomnih koeficijenata:
Alternativan izraz je:
Rekurzija
[uredi | uredi izvor]Katalanovi brojevi zadovoljavaju rekurziju:
- za
Pošto je onda je:
- .
Zadovoljavaju i sledeću rekurziju:
Svojstva
[uredi | uredi izvor]Generirajuća funkcija Katalanovih brojeva je:
Asimptotska vrednost je:
Kombinatorika
[uredi | uredi izvor]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 trouglova. Na slici je prikazan primer za slučaj n = 4:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
Potpuno binarno stablo, gde svaki verteks ima ili dvoje dece ili je bez dece, može da predstavlja primer za Katalanove brojeve. Katalanovi broj je broj potpunih binarnih stabala sa n + 1 listom.
![](http://upload.wikimedia.org/wikipedia/commons/0/01/Catalan_number_binary_tree_example.png)
Literatura
[uredi | uredi izvor]- Katalanovi brojevi
- Koshy, Thomas , Catalan Numbers with Applications. . Oxford University Press. 2008. ISBN 978-0-19-533454-8.