Siirry sisältöön

Catalanin luku

Wikipediasta
Viidelle elementille on olemassa C5 = 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:

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;
    }
}
  1. a b A000108 OEIS-tietokannassa
  2. a b Eric W. Weisstein: Catalan Number mathworld.wolfram.com. Viitattu 26.4.2025. (englanniksi)
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.