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:

Ensimmäiset Catalanin luvut ovat (n arvoilla 0, 1, 2..):

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.