Kombinatoriikassa Catalanin luvut on joukko luonnollisia lukuja, jotka esiintyvät monenlaisissa laskentaongelmissa, jotka käsittelevät usein rekursiivisesti määriteltyjä objekteja. Luvut ovat nimetty belgialaisen matemaatikon Eugène Charles Catalanin mukaan.
n:s Catalanin luku lasketaan binomikertoimilla seuraavasti:
Rekursiivinen laskutapa:
Toinen rekursio on:
Pätee myös:
Ensimmäiset Catalanin luvut (n:n arvoilla 0, 1, 2, …) ovat 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, …
Ohjelmallinen toteutus Catalanin luvut ovat laskettavissa JavaScriptillä rekursiolla seuraavalla funktiolla:
function catalan(n) { if (n == 0) { return 1; } else if (n > 0) { m = 0; for (let i = 0; i < n; ++i) { m += catalan(i) * catalan(n-i-1);
return m;
Lähteet
Luokka:Kombinatoriikka