Catalanin luvun laskin
Etsi n:s Catalanin luku ja näe, miten jono 1, 1, 2, 5, 14, 42, … räjähtää n:n kasvaessa.
Counts balanced parentheses, full binary trees and polygon triangulations.
- 1
Seed value C₀ = 1
1 - 2
Recurrence ratio for step n
2 × (2 × 8 − 1) ÷ (8 + 1) = 3,333333Each Catalan number equals the previous term multiplied by 2(2n−1)/(n+1). - 3
Previous term C7
429 - 4
C8 = C7 × ratio
429 × 3,333333 = 1 430
Miten tämä laskin toimii?
n:s Catalanin luku on Cₙ = C(2n, n)/(n+1) = (2n)!/((n+1)!·n!). Se laskee tasapainotetut sulkeet, täydet binääripuut, hilapolut ja monikulmion kolmiojaot. Jono alkaa 1, 1, 2, 5, 14, 42, 132, … ja kasvaa suunnilleen kuten 4ⁿ. Syötä mikä tahansa kokonaisluku n ≥ 0 saadaksesi Cₙ:n ja koko kasvukäyrän.
Kaava
How this is calculated
Syötä ei-negatiivinen kokonaisluku n. Catalanin luvut Cₙ laskevat valtavan perheen kombinatorisia objekteja: tapojen lukumäärän, joilla n sulkuparia voidaan oikein yhdistää, täysien binääripuiden lukumäärän, joilla on n+1 lehteä, monotonisten hilapolkujen lukumäärän, jotka pysyvät lävistäjän alapuolella, ja kuperan (n+2)-kulmion kolmiojakojen lukumäärän — kaikki yhtä kuin sama Cₙ.
Suljettu muoto on Cₙ = (2n)! / ((n+1)! · n!), vastaten keskeistä binomikerrointa C(2n, n) jaettuna (n+1):llä. Kertomien laskeminen suoraan ylivuotaa nopeasti, joten tämä laskin käyttää tarkkaa kokonaislukurekursiota C₀ = 1 ja C_{k+1} = C_k · 2(2k+1)/(k+2). Jokainen askel kertoo kokonaislukuarvoisella tekijällä pitäen kulkevan arvon tarkkana niin kauan kuin kaksoistarkkuus sallii ja rakentaen koko jonon C₀…Cₙ kasvukäyrään piirrettynä.
Arvot ovat ulottuvuudettomia lukumääriä, joten vain kokonaisluku n ≥ 0 on mielekäs; murtolukusyöte pyöristetään alaspäin. Koska Cₙ kasvaa suunnilleen kuten 4ⁿ / (n^{3/2}√π), luvut ylittävät 64-bittisen liukuluvun tarkan kokonaislukualueen noin n = 30 jälkeen ja ylivuotavat kokonaan noin n ≈ 170 jälkeen, joten syöte rajataan arvoon 170 ja suuret tulokset näytetään tieteellisessä merkinnässä.
Usein kysytyt kysymykset
Jono alkaa C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, C₇ = 429 ja C₈ = 1430.
Rekursiosta Cₙ/Cₙ₋₁ = 2(2n−1)/(n+1), joka lähestyy 4:ää n:n kasvaessa. Tämä heijastaa asymptoottista kasvua Cₙ ≈ 4ⁿ / (n^{3/2}√π).
Catalanin luvut kasvavat eksponentiaalisesti. Yli n ≈ 170 arvo ylittää suurimman esitettävissä olevan kaksoistarkkuusluvun (~1,8×10³⁰⁸), joten suurempia syötteitä ei voida laskea tarkasti standardilla liukuluvulla.
Tunnetaan myös nimellä
TG we-Calculate Editorial Team. (2026). Catalanin luvun laskin [Online calculator]. TG we-Calculate. https://we-calculate.com/fi/calculator/catalan-number-calculator
TG we-Calculate Editorial Team. "Catalanin luvun laskin." TG we-Calculate. 2026. https://we-calculate.com/fi/calculator/catalan-number-calculator.
TG we-Calculate Editorial Team, "Catalanin luvun laskin," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/fi/calculator/catalan-number-calculator
@misc{wecalculate_catalan_number_calculator, title = {Catalanin luvun laskin}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/fi/calculator/catalan-number-calculator}}, year = {2026}, note = {TG we-Calculate} }
Oliko tästä laskimesta sinulle apua?