Katalano skaičių skaičiuoklė
Raskite n-ąjį Katalano skaičių ir pamatykite, kaip seka 1, 1, 2, 5, 14, 42, … sprogsta augant n.
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
Kaip veikia ši skaičiuoklė?
n-asis Katalano skaičius yra Cₙ = C(2n, n)/(n+1) = (2n)!/((n+1)!·n!). Jis skaičiuoja subalansuotus skliaustus, pilnus dvejetainius medžius, gardelės kelius ir daugiakampių trianguliacijas. Seka prasideda 1, 1, 2, 5, 14, 42, 132, … ir auga maždaug kaip 4ⁿ. Įveskite bet kurį sveikąjį skaičių n ≥ 0, kad gautumėte Cₙ ir visą augimo kreivę.
Formulė
How this is calculated
Įveskite neneigiamą sveikąjį skaičių n. Katalano skaičiai Cₙ skaičiuoja milžinišką kombinatorinių objektų šeimą: kelis būdus teisingai suderinti n skliaustų porų, pilnų dvejetainių medžių su n+1 lapais skaičių, monotoninių gardelės kelių, kurie lieka po įstrižaine, skaičių ir iškilo (n+2)-kampio trianguliacijų skaičių – visi lygūs tam pačiam Cₙ.
Uždaroji forma yra Cₙ = (2n)! / ((n+1)! · n!), arba centrinis binominis koeficientas C(2n, n), padalytas iš (n+1). Tiesioginis faktorialų skaičiavimas greitai persipildo, todėl ši skaičiuoklė naudoja tikslią sveikaskaitę rekurenciją C₀ = 1 ir C_{k+1} = C_k · 2(2k+1)/(k+2). Kiekvienas žingsnis dauginamas iš sveikaskaičio daugiklio, išlaikydamas einamąją reikšmę tikslią kiek leidžia dvigubas tikslumas, ir sudaro visą seką C₀…Cₙ, atvaizduojamą augimo kreivėje.
Reikšmės yra bedimensiniai skaičiai, todėl prasmingas tik sveikasis n ≥ 0; trupmeninė įvestis suapvalinama žemyn. Kadangi Cₙ auga maždaug kaip 4ⁿ / (n^{3/2}√π), skaičiai viršija tikslų 64 bitų slankiojo kablelio sveikąjį diapazoną maždaug po n = 30 ir visiškai persipildo po n ≈ 170, todėl įvestis apribota iki 170, o dideli rezultatai rodomi moksline notacija.
Dažnai užduodami klausimai
Seka prasideda C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, C₇ = 429 ir C₈ = 1430.
Iš rekurencijos Cₙ/Cₙ₋₁ = 2(2n−1)/(n+1), kuris augant n artėja prie 4. Tai atspindi asimptotinį augimą Cₙ ≈ 4ⁿ / (n^{3/2}√π).
Katalano skaičiai auga eksponentiškai. Po n ≈ 170 reikšmė viršija didžiausią išreiškiamą dvigubo tikslumo skaičių (~1,8×10³⁰⁸), todėl didesnių įvesčių negalima apskaičiuoti tiksliai standartiniu slankiuoju kableliu.
Taip pat žinomas kaip
TG we-Calculate Editorial Team. (2026). Katalano skaičių skaičiuoklė [Online calculator]. TG we-Calculate. https://we-calculate.com/lt/calculator/catalan-number-calculator
TG we-Calculate Editorial Team. "Katalano skaičių skaičiuoklė." TG we-Calculate. 2026. https://we-calculate.com/lt/calculator/catalan-number-calculator.
TG we-Calculate Editorial Team, "Katalano skaičių skaičiuoklė," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/lt/calculator/catalan-number-calculator
@misc{wecalculate_catalan_number_calculator, title = {Katalano skaičių skaičiuoklė}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/lt/calculator/catalan-number-calculator}}, year = {2026}, note = {TG we-Calculate} }
Ar ši skaičiuoklė jums padėjo?