Kalkulator Liczb Catalana
Wyznacz n-tą liczbę Catalana i przekonaj się, jak ciąg 1, 1, 2, 5, 14, 42, … rośnie w miarę wzrostu 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 = 1430
Jak działa ten kalkulator?
n-ta liczba Catalana to Cₙ = C(2n, n)/(n+1) = (2n)!/((n+1)!·n!). Zlicza zrównoważone nawiasy, pełne drzewa binarne, ścieżki siatkowe i triangulacje wielokątów. Ciąg zaczyna się od 1, 1, 2, 5, 14, 42, 132, … i rośnie w przybliżeniu jak 4ⁿ. Wprowadź dowolną liczbę całkowitą n ≥ 0, aby uzyskać Cₙ i pełną krzywą wzrostu.
Wzór
How this is calculated
Wprowadź nieujemną liczbę całkowitą n. Liczby Catalana Cₙ zliczają ogromną rodzinę obiektów kombinatorycznych: liczbę sposobów prawidłowego dopasowania n par nawiasów, liczbę pełnych drzew binarnych z n+1 liśćmi, liczbę monotonicznych ścieżek siatkowych pozostających poniżej przekątnej oraz liczbę triangulacji wypukłego (n+2)-kąta — wszystkie równe temu samemu Cₙ.
Postać zamknięta to Cₙ = (2n)! / ((n+1)! · n!), czyli centralny współczynnik dwumianowy C(2n, n) podzielony przez (n+1). Bezpośrednie obliczanie silni szybko powoduje przepełnienie, dlatego kalkulator używa dokładnej całkowitoliczbowej rekurencji C₀ = 1 i C_{k+1} = C_k · 2(2k+1)/(k+2). Każdy krok mnoży przez czynnik o wartości całkowitej, utrzymując bieżącą wartość dokładną tak długo, jak pozwala arytmetyka podwójnej precyzji, i buduje pełny ciąg C₀…Cₙ widoczny na wykresie wzrostu.
Wartości są bezwymiarowymi ilościami, więc sensowna jest jedynie całkowita n ≥ 0; wejście ułamkowe jest zaokrąglane w dół. Ponieważ Cₙ rośnie w przybliżeniu jak 4ⁿ / (n^{3/2}√π), liczby przekraczają dokładny zakres całkowitoliczbowy 64-bitowej liczby zmiennoprzecinkowej powyżej ok. n = 30 i całkowicie przepełniają się powyżej n ≈ 170, więc wejście jest ograniczone do 170, a duże wyniki wyświetlane są w notacji naukowej.
Najczęściej zadawane pytania
Ciąg zaczyna się od C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, C₇ = 429 i C₈ = 1430.
Z rekurencji wynika, że Cₙ/Cₙ₋₁ = 2(2n−1)/(n+1), co dąży do 4 w miarę wzrostu n. Odzwierciedla to asymptotyczny wzrost Cₙ ≈ 4ⁿ / (n^{3/2}√π).
Liczby Catalana rosną wykładniczo. Powyżej n ≈ 170 wartość przekracza maksymalną reprezentowalną liczbę podwójnej precyzji (~1,8×10³⁰⁸), więc większych wejść nie można obliczyć dokładnie przy użyciu standardowej arytmetyki zmiennoprzecinkowej.
Znany również jako
TG we-Calculate Editorial Team. (2026). Kalkulator Liczb Catalana [Online calculator]. TG we-Calculate. https://we-calculate.com/pl/calculator/catalan-number-calculator
TG we-Calculate Editorial Team. "Kalkulator Liczb Catalana." TG we-Calculate. 2026. https://we-calculate.com/pl/calculator/catalan-number-calculator.
TG we-Calculate Editorial Team, "Kalkulator Liczb Catalana," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/pl/calculator/catalan-number-calculator
@misc{wecalculate_catalan_number_calculator, title = {Kalkulator Liczb Catalana}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/pl/calculator/catalan-number-calculator}}, year = {2026}, note = {TG we-Calculate} }
Czy ten kalkulator Ci pomógł?