Ero sivun ”Catalanin luku” versioiden välillä
| [katsottu versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
rekursiivinen kaava |
||
Rivi 1:
[[File:Noncrossing partitions 5.svg|thumb|Viidelle elementille on olemassa {{nowrap|1=C<sub>5</sub> = 42}} erilaista ei-päällekkäistä partitiota sekä vielä 10 päällekkäistä partitiota (alla). 42 + 10 = 52 on niin sanottu [[Bellin luku]].]]
[[Kombinatoriikka|Kombinatoriikassa]] '''Catalanin luvut''' on joukko [[luonnollinen luku|luonnollisia lukuja]], jotka esiintyvät monenlaisissa laskentaongelmissa, jotka käsittelevät usein [[rekursio|rekursiivisesti]] määriteltyjä objekteja. Luvut ovat nimetty [[belgia]]laisen [[matemaatikko|matemaatikon]] [[Eugène Charles Catalan]]in mukaan.
''n'':s Catalanin luku lasketaan [[binomikerroin|binomikertoimilla]] seuraavasti:
:<math>C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ kun }n\ge 0.</math>
[[Rekursiivinen jono|Rekursiivinen]] laskutapa:<ref name="oeis">{{OEIS|A000108}}</ref>
:<math>C_0 = 1; \ C_n = {2(2n-1)C_{n-1} \over n+1}</math>
Ensimmäiset Catalanin luvut (''n'':n arvoilla 0, 1, 2, …) ovat 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, …<ref name="oeis"/>
== Lähteet ==
{{Viitteet}}
{{tynkä/Matematiikka}}
| |||