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.

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.

n:s Catalanin luku lasketaan binomikertoimilla seuraavasti:

Rekursiivinen laskutapa:[1]

Ensimmäiset Catalanin luvut (n:n arvoilla 0, 1, 2, …) ovat 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, …[1]

LähteetMuokkaa

  1. a b A000108 OEIS-tietokannassa
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.