Katalanov broj

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 belgijskog matematičara Eugèna Charlesa Catalana.

DefinicijaUredi

Definišu se preko binomnih koeficijenata:

  za  

Alternativan izraz je:

  za  

RekurzijaUredi

Katalanovi brojevi zadovoljavaju rekurziju:

  за  

Kako je   tada je:

 .

Zadovoljavaju i sljedeću rekurziju

 

OsobineUredi

Generirajuća funkcija Katalanovih brojeva je:

 

Asimptotska vrijednost je:

 

Vanjski linkoviUredi