Catalani arvude kalkulaator
Arvuta Catalani arve, mida kasutatakse kombinatoorikas ja binaarpuudes
Sisesta mittenegatiivne täisarv (0 kuni 30)
Tulemused
Sisesta väärtused ja klõpsa Arvuta, et näha tulemust.
Teooria ja valem
Catalani arvud
Catalani arvud moodustavad naturaalarvude jada, mis esineb paljudes loendamisülesannetes. n-is Catalani arv loendab muu hulgas n sulupaari korrektseid järjestusi.
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} \quad(n \ge 1),\quad C_0=1\)
Esimene valem kasutab binoomkordajaid, 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
- Viiside arv, kuidas jaotada n+2 küljega kumer hulknurk kolmnurkadeks
- Viiside arv, kuidas ühendada 2n punkti ringjoonel n mitteristuva kõõluga
Esimesed Catalani arvud
Esimesed mõned Catalani arvud on: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Näide
Arvuta C₃ ehk kolme sulupaari korrektsete järjestuste arv:
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)