Catalani arvude kalkulaator
Arvuta Catalani arve, mida kasutatakse kombinatoorikas ja binaarpuudes
Sisesta mitte-negatiivne täisarv (0 kuni 30)
Tulemused
Sisesta väärtused ja klõpsa Arvuta, et näha tulemust.
Teooria ja valem
Catalani numbrid
Catalani numbrid moodustavad naturaalarvude jada, mis esineb erinevates loendamisülesannetes, sageli rekursiivselt määratletud objektidega. n-ndat Catalani arvu kasutatakse avalduste arvutamiseks, mis sisaldavad n paari õigesti sobitatud sulgusid.
Valemid
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
Esimene valem kasutab binomiaalkoefitsiente, teine on rekursiivne määratlus
Rakendused
- Viiside arv, kuidas õigesti sobitada n paari sulgusid
- Erinevate binaarpuude arv, millel on n+1 lehte
- Teede arv punktist (0,0) punkti (n,n), mis ei ületa diagonaali
- Viisid kumerate hulknurkade, millel on n+2 külge, kolmnurkadeks jagamiseks
- Viisid ühendada 2n punkti ringjoonel n ristumata kõrvutisega
Esimesed Catalani arvud
Esimesed mõned Catalani arvud on: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Näide
Arvuta C₃ (viisid 3 paar sulgude sobitamiseks):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)