Catalanin luku

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