Catalanin luku

Viidelle elementille on olemassa C₅ = 42 erilaista ei-päällekkäistä partitiota sekä vielä 10 päällekkäistä partitiota (alla). 42 + 10 = 52 on niin sanottu Bellin 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:

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ kun }}n\geq 0.$

Rekursiivinen laskutapa:

$C_{0}=1;\ C_{n}={2(2n-1)C_{n-1} \over n+1}$

Toinen rekursio on:

$C_{n}=\sum _{k=0}^{n-1}C_{k}C_{n-k-1}$

Pätee myös:

${\frac {C_{n+1}}{C_{n}}}={\frac {2(2n+1)}{n+2}}$

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;
    }
}