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 C₅ = 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:

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

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