Catalan-szám kalkulátor
Határozd meg az n-edik Catalan-számot, és nézd meg, hogyan robban fel az 1, 1, 2, 5, 14, 42, … sorozat az n növekedtével.
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 = 1430
Hogyan működik ez a kalkulátor?
Az n-edik Catalan-szám Cₙ = C(2n, n)/(n+1) = (2n)!/((n+1)!·n!). Kiegyensúlyozott zárójeleket, teljes bináris fákat, rácsutakat és sokszög-háromszögeléseket számol. A sorozat 1, 1, 2, 5, 14, 42, 132, …-vel kezdődik, és körülbelül 4ⁿ-ként nő. Adj meg bármely n ≥ 0 egész számot, hogy megkapd Cₙ-t és a teljes növekedési görbét.
Képlet
How this is calculated
Adj meg egy nemnegatív n egész számot. A Cₙ Catalan-számok kombinatorikai objektumok hatalmas családját számolják: ahányféleképp helyesen párosítható n zárójelpár, ahány teljes bináris fa van n+1 levéllel, ahány monoton rácsút marad az átló alatt, és ahány háromszögelése van egy konvex (n+2)-szögnek — mind ugyanazzal a Cₙ-nel egyenlő.
A zárt alak Cₙ = (2n)! / ((n+1)! · n!), egyenértékűen a központi binomiális együttható C(2n, n) osztva (n+1)-gyel. A faktoriálisok közvetlen kiszámítása gyorsan túlcsordul, ezért ez a kalkulátor a pontos egész rekurziót használja: C₀ = 1 és C_{k+1} = C_k · 2(2k+1)/(k+2). Minden lépés egy egész értékű tényezővel szoroz, így a futó értéket addig tartja pontosan, ameddig a dupla precizitás engedi, és felépíti a teljes C₀…Cₙ sorozatot a növekedési görbén.
Az értékek mértékegység nélküli megszámlálások, így csak egész n ≥ 0 értelmes; a törtbemenetet lefelé kerekíti. Mivel Cₙ nagyjából 4ⁿ / (n^{3/2}√π) szerint nő, a számok körülbelül n = 30 felett meghaladják egy 64 bites lebegőpontos szám pontos egész tartományát, és n ≈ 170 felett teljesen túlcsordulnak, ezért a bemenet 170-re van korlátozva, a nagy eredmények pedig tudományos jelölésben jelennek meg.
Gyakran ismételt kérdések
A sorozat így kezdődik: C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, C₇ = 429 és C₈ = 1430.
A rekurzióból Cₙ/Cₙ₋₁ = 2(2n−1)/(n+1), amely 4-hez tart, ahogy n nő. Ez tükrözi a Cₙ ≈ 4ⁿ / (n^{3/2}√π) aszimptotikus növekedést.
A Catalan-számok exponenciálisan nőnek. n ≈ 170 felett az érték meghaladja a legnagyobb ábrázolható dupla precizitású számot (~1,8×10³⁰⁸), így a nagyobb bemenetek nem számolhatók ki pontosan szabványos lebegőponttal.
Más néven
TG we-Calculate Editorial Team. (2026). Catalan-szám kalkulátor [Online calculator]. TG we-Calculate. https://we-calculate.com/hu/calculator/catalan-number-calculator
TG we-Calculate Editorial Team. "Catalan-szám kalkulátor." TG we-Calculate. 2026. https://we-calculate.com/hu/calculator/catalan-number-calculator.
TG we-Calculate Editorial Team, "Catalan-szám kalkulátor," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/hu/calculator/catalan-number-calculator
@misc{wecalculate_catalan_number_calculator, title = {Catalan-szám kalkulátor}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/hu/calculator/catalan-number-calculator}}, year = {2026}, note = {TG we-Calculate} }
Segített ez a kalkulátor?