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ä. N:s Catalanin luku laskee lausekkeiden määrän, jotka sisältävät n paria sulkuja, jotka on oikein yhdistetty.
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}\)
Ensimmäinen kaava käyttää binomikertoimia, kun taas toinen on rekursiivinen määritelmä
Sovellukset
- Tapausten lukumäärä, joilla n paria sulkuja voidaan yhdistää oikein
- Eri binaaripuiden 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ä yhdistää 3 sulkuparia):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)