Catalanin luku

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:

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

Rekursiivinen laskutapa:[1]

C 0 = 1 ;   C n = 2 ( 2 n − 1 ) C n − 1 n + 1 {\displaystyle 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, …[1]

Lähteet

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