Catalani arvude kalkulaator
Arvuta Catalani arve kombinatoorika ja binaarpuude rakendustega
Sisesta mittenegatiivne täisarv (0 kuni 30)
Tulemused
Sisesta väärtused ja klõpsa Arvuta, et näha tulemust.
Theory & Formula
Catalani arvud
Catalani arvud moodustavad naturaalarvude jada, mis ilmub erinevates loendamise ülesannetes, sageli rekursiivselt defineeritud objektidega. N-s Catalani arv loendab avaldiste arvu, mis sisaldavad n sulgupaari ja on õigesti paigutatud.
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 definitsioon
Rakendused
- Viiside arv õigesti paigutada n sulgupaari
- Erinevate binaarpuude arv n+1 lehega
- Teede arv (0,0)-st (n,n)-ni, mis ei ületa diagonaali
- Viiside arv kolmnurgastada kumerat hulknurka n+2 küljega
- Viiside arv ühendada 2n punkti ringil n ristumatu kõõluga
Esimesed Catalani arvud
Esimesed Catalani arvud on: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Näide
Arvuta C₃ (viiside arv paigutada 3 sulgupaari):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)