Katalanovi brojevi

S Vikipedije, slobodne enciklopedije

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:

Catalan-Hexagons-example.svg

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.

Catalan number binary tree example.png

Literatura[uredi | uredi izvor]