Catalan-lukujen laskin
Laske Catalan-lukuja, joilla on sovelluksia kombinatoriikassa ja binääripuissa
Anna ei-negatiivinen kokonaisluku (0–30)
Tulokset
Syötä arvot ja napsauta Laske nähdäksesi tuloksen.
Teoria ja kaava
Catalanin luvut
Catalanin luvut muodostavat luonnollisten lukujen jonon, joka esiintyy erilaisissa laskentatehtävissä, usein rekursiivisesti määriteltyjen kohteiden yhteydessä. Catalanin luvuista n:s on niiden lausekkeiden lukumäärä, joissa n sulkuparia on yhdistetty oikein.
Kaavat
\(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\)
Ensimmäinen kaava käyttää binomikertoimia, kun taas toinen on rekursiivinen määritelmä
Sovellukset
- Tapojen lukumäärä, joilla n paria sulkuja voidaan yhdistää oikein
- Eri binääripuiden lukumäärä, joissa on n+1 lehteä
- Polkujen lukumäärä pisteestä (0,0) pisteeseen (n,n), jotka eivät ylitä diagonaalia
- Tavat trianguloida (n+2)-sivuinen konveksi monikulmio
- Tavat yhdistää 2n pistettä ympyrällä n ei-leikkaavalla jänteellä
Ensimmäiset Catalan-luvut
Ensimmäiset muutamat Catalan-luvut ovat: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Esimerkki
Laske C₃ (tapojen lukumäärä, joilla 3 sulkuparia voidaan yhdistää):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)