Catalanin luku
Ulkoasu

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:[1]
Toinen rekursio on:[2]
Pätee myös:[2]
Ensimmäiset Catalanin luvut (n:n arvoilla 0, 1, 2, …) ovat 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, …[1]
Ohjelmallinen toteutus
[muokkaa | muokkaa wikitekstiä]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;
}
}