PL 
EnglishDomyślny
Українська🔢 Liczby Catalana
Jeden ciąg zlicza je wszystkie: poprawne nawiasowania, ścieżki Dycka, drzewa binarne, triangulacje wielokątów i nieprzecinające się cięciwy. Rysuj obiekty i patrz, jak Cₙ₊₁/Cₙ dąży do 4.
O liczbach Catalana
Liczby Catalana C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, … to jeden z najbardziej wszechobecnych ciągów w kombinatoryce, pojawiający się w dziesiątkach pozornie niepowiązanych problemów zliczania. Wzór Cₙ = (2n)! / ((n+1)! n!) był badany przez Eulera, Segnera i Catalana w XVIII i XIX wieku. Kluczowa obserwacja, potwierdzona istnieniem jawnych bijekcji (odpowiedniości jeden do jednego), polega na tym, że zbalansowane ciągi nawiasów, ścieżki kratowe Dycka, pełne drzewa binarne, triangulacje wielokąta wypukłego oraz diagramy cięciw bez przecięć są liczone przez dokładnie tę samą liczbę Cₙ — dlatego rozwiązanie jednego problemu automatycznie rozwiązuje wszystkie pozostałe.
Ta symulacja pozwala jednocześnie eksplorować wszystkie pięć bijekcji dla n od 0 do 8. Wybierz „Pokaż wszystkie", aby wyświetlić od razu każdy obiekt Cₙ, lub „Próbkuj", aby animować losowe przejście przez zbiór. Wykres słupkowy poniżej pokazuje ciąg Catalana C₀ … Cₙ rosnący wykładniczo (Cₙ ~ 4ⁿ / (n^(3/2) √π)), a panel wzoru aktualizuje się na bieżąco podczas przechodzenia przez obiekty, pokazując zarówno jawny wzór, jak i stosunek C_(n+1)/Cₙ zbiegający do 4.
Najczęściej zadawane pytania
Czym jest liczba Catalana?
Cₙ to liczba sposobów wykonania zadania kombinatorycznego o określonej strukturze rekurencyjnej — dokładniej, każdego zadania, które można podzielić na dwa niezależne podzadania o rozmiarach 0 i n–1, lub 1 i n–2, …, lub n–1 i 0. Wzór jawny to Cₙ = (2n)! / ((n+1)! n!) = C(2n, n) / (n+1), gdzie C(2n, n) to centralny współczynnik dwumianowy. Pierwsze wartości to 1, 1, 2, 5, 14, 42, 132, 429, 1430, a ciąg rośnie asymptotycznie jak Cₙ ~ 4ⁿ / (n^(3/2) √π).
Czym są zbalansowane ciągi nawiasów i jak wiążą się z Cₙ?
Zbalansowany ciąg nawiasów o długości 2n to sekwencja n nawiasów otwierających „(" i n nawiasów zamykających „)", w której żaden prefiks nie zawiera więcej „)" niż „(". Dla n = 3 istnieje dokładnie C₃ = 5 takich ciągów: ((())), (()()), (())(), ()(()), ()()(). Ciągi te pojawiają się przy analizie wyrażeń, poprawnym zagnieżdżaniu HTML oraz w problemie permutacji sortowalnych za pomocą stosu. Bijekcja do ścieżek Dycka jest bezpośrednia: „(" odpowiada krokowi w górę, a „)" krokowi w dół, więc zasada braku ujemnego prefiksu staje się zasadą nieschodzenia poniżej osi.
Czym jest ścieżka Dycka?
Ścieżka Dycka długości 2n to ścieżka kratowa od (0, 0) do (2n, 0), która wykonuje n kroków w górę (+1) i n kroków w dół (−1) i nigdy nie schodzi poniżej osi x. Istnieje Cₙ takich ścieżek. Były badane przez niemieckiego matematyka Walthera von Dycka i pojawiają się w analizie sekwencji głosowania (prawdopodobieństwo, że kandydat A jest ściśle na prowadzeniu przez cały czas liczenia głosów), błądzeniach losowych, które muszą pozostać nieujemne, oraz w wyliczaniu sekwencji w teorii języków formalnych (np. poprawne programy w Lispie z dopasowanymi nawiasami).
Jak triangulacja wielokąta wypukłego daje Cₙ?
Wypukły (n+2)-kąt można podzielić na trójkąty, rysując n–1 nieprzecinających się przekątnych; liczba sposobów wykonania tego to Cₙ. Dla czworokąta (n = 2): dwie triangulacje. Dla pięciokąta (n = 3): pięć triangulacji. Bijekcja do ciągów nawiasów działa poprzez ustalenie jednej krawędzi wielokąta jako „korzenia" i zauważenie, że trójkąt na tej krawędzi dzieli pozostały wielokąt na dwa mniejsze wielokąty, odzwierciedlając rekurencję Catalana Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ. Triangulacje pojawiają się w geometrii obliczeniowej (optymalna triangulacja wielokąta, triangulacja Delaunaya), metodach numerycznych (siatkowanie metodą elementów skończonych) oraz projektowaniu kompilatorów (drzewa składniowe).
Czym są diagramy cięciw bez przecięć?
Diagram cięciw bez przecięć składa się z 2n punktów na okręgu połączonych n nieprzecinającymi się cięciwami. C₃ = 5 sposobów połączenia 6 punktów 3 nieprzecinającymi się cięciwami to dokładnie pięć obiektów Catalana dla n = 3. Diagramy te pojawiają się w przewidywaniu struktury drugorzędowej RNA (pary zasad to nieprzecinające się cięciwy na sekwencji), teorii węzłów (algebry Temperleya–Lieba) oraz probabilistyce wolnej (nieprzecinające się podziały definiują wolne kumulanty rozkładów probabilistycznych). Liczba nieprzecinających się podziałów zbioru {1, …, n} to również Cₙ.
Jaka jest zależność rekurencyjna dla liczb Catalana?
Liczby Catalana spełniają rekurencję C₀ = 1 oraz Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. Ten wzór odzwierciedla strukturę „podziału przy korzeniu" wspólną dla wszystkich pięciu rodzin bijektywnych: w ciągu nawiasów korzeniowy „(" zamyka się w pewnej pozycji, dzieląc ciąg na dwa niezależne zbalansowane podciągi o długościach 2i i 2(n–i). Sumowanie po wszystkich pozycjach podziału daje rekurencję. Funkcja tworząca C(x) = Σ Cₙ xⁿ spełnia x C(x)² – C(x) + 1 = 0, z rozwiązaniem C(x) = (1 – √(1 – 4x)) / (2x).
Dlaczego tak wiele problemów kombinatorycznych daje liczby Catalana?
Jednocząca przyczyna jest taka, że wszystkie rodziny Catalana mają tę samą strukturę rekurencyjną: obiekt o rozmiarze n można jednoznacznie skonstruować, wybierając „korzeń", który dzieli pozostałe dane na dwa niezależne podobiekty o rozmiarach i oraz n–1–i (lub podobnych), sumując po wszystkich podziałach. To dokładnie rekurencja Catalana. Bijekcje między tymi rodzinami są często eleganckie: „(" w ciągu nawiasów staje się krawędzią lewego dziecka w drzewie binarnym i krokiem w górę w ścieżce Dycka, więc dane kombinatoryczne to dosłownie ten sam obiekt w trzech różnych przebraniach.
Jak szybko rosną liczby Catalana?
Liczby Catalana rosną wykładniczo: zgodnie z przybliżeniem Stirlinga, Cₙ ~ 4ⁿ / (n^(3/2) √π). Stosunek Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) zbiega do 4, więc każda kolejna liczba Catalana jest w przybliżeniu cztery razy większa od poprzedniej. C₁₀ = 16 796; C₂₀ ≈ 6,56 × 10¹⁰; C₅₀ ≈ 1,37 × 10²⁸. Dla n = 8 (maksimum w tej symulacji) C₈ = 1430 — wystarczająco mało, by narysować wszystkie obiekty osobno. Powyżej n ≈ 10 wyliczenie ich wszystkich staje się niepraktyczne i trzeba stosować losowe próbkowanie.
Czym są pełne drzewa binarne i jak liczą Cₙ?
Pełne drzewo binarne to drzewo zakorzenione, w którym każdy węzeł wewnętrzny ma dokładnie dwoje dzieci (nigdy jedno). Liczba pełnych drzew binarnych z n+1 liśćmi to Cₙ. Dla n = 3: C₃ = 5 drzew z 4 liśćmi. Bijekcja do ciągów nawiasów przypisuje każdemu liściowi „)", a każdemu węzłowi wewnętrznemu „(", odczytując drzewo od lewej do prawej w porządku preorder. Pełne drzewa binarne to struktura analizy składniowej wyrażeń, kodowania Huffmana i drzewa Sterna–Brocota dla ułamków. Liczą też liczbę sposobów pełnego nawiasowania iloczynu n+1 czynników — pierwotne sformułowanie problemu przez Eulera (1751).
Kto pierwszy odkrył liczby Catalana?
Euler liczył triangulacje wielokątów w 1751 roku i znalazł ciąg 1, 2, 5, 14, 42, … lecz nie miał wzoru jawnego. Segner znalazł rekurencję w 1758 roku. Belgijski matematyk Eugène Charles Catalan podał jawny wzór Cₙ = (2n)!/((n+1)!n!) w 1838 roku, a ciąg od tej pory nosi jego nazwisko. Jednak ciąg ten został odkryty jeszcze wcześniej przez chińskiego matematyka Minga Antu około 1730 roku w związku ze wzorami rozwinięć trygonometrycznych. Historia tych równoczesnych, niezależnych odkryć jest wyrazistym przykładem uniwersalności matematyki.
Gdzie liczby Catalana pojawiają się poza czystą matematyką?
Liczby Catalana pojawiają się w informatyce (liczba permutacji sortowalnych za pomocą stosu, liczba różnych drzew BST z n kluczami, liczba monotonicznych funkcji boolowskich na 2 zmiennych), bioinformatyce (struktury drugorzędowe RNA zliczane przez ich nieprzecinającą się strukturę nawiasów), fizyce (nieprzecinające się diagramy Feynmana w płaskiej kwantowej teorii pola, momenty rozkładu półkolistego Wignera w teorii macierzy losowych) oraz lingwistyce (liczba drzew rozbioru dla niejednoznacznej gramatyki bezkontekstowej o określonej strukturze reguł). Książka Stanleya „Catalan Numbers" (2015) wymienia 214 odrębnych interpretacji kombinatorycznych.