Liczby Catalana: Sekwencja Licząca Wszystko

Definicja

N-ty wyraz ciągu liczb katalanowych, oznaczany jako C(n), jest zdefiniowany jako 1 podzielone przez (n+1), pomnożone przez współczynnik dwumianowy (2n po n). Alternatywnie można go zapisać bez dzielenia, jako (2n po n) minus (2n po n+1), co odpowiada liczbie otrzymanej z dwóch sąsiednich współczynników dwumianowych w trójkącie Pascala. Ciąg zaczyna się od C(0) = 1, C(1) = 1, C(2) = 2, C(3) = 5, C(4) = 14, C(5) = 42, C(6) = 132 i szybko rośnie – każdy wyraz jest liczbą całkowitą, mimo że wzór zawiera dzielenie, co samo w sobie stanowi małe, ale zauważalne, matematyczne znanie.

C(n) = 1/(n+1) * C(2n, n) = C(2n, n) - C(2n, n+1)

worked example, n = 3:
  C(6, 3) = 20
  C(3) = 20 / (3+1) = 20 / 4 = 5

n :  0   1   2   3   4    5    6
Cn:  1   1   2   5  14   42  132

Rekurencja – i dlaczego pojawia się ona wszędzie

Liczby Catalana również spełniają rekurencję: C(0) = 1, oraz C(n+1) równa się sumie, w przedziale od 0 do n, wyrazów C(i) pomnożonych przez C(n-i). Ta konwolucja wynika bezpośrednio z podziału struktury o rozmiarze n+1 na część lewą o rozmiarze i oraz część prawą o rozmiarze n-i – obie części są niezależne, więc liczba sposobów zbudowania całego elementu jest iloczynem liczb sposobów zbudowania każdego z nich, zsumowaną dla każdego możliwego punktu podziału. To jedno pojęcie wyjaśnia, dlaczego ta sama sekwencja pojawia się w strukturach, które niczym przypominają siebie nawzajem: każdy obiekt, który można rozłożyć w ten sam sposób – mniejsza część zawarta lub przytwierdzona do mniejszej pozostałej części – przestaje podlegać tej rekurencji i tym samym jest zliczany przez liczby Catalana.

Zbalansowane nawiasy i ścieżki Dycka

C(n) liczy liczbę sposobów ułożenia n par zbalansowanych nawiasów. Dla n = 3 istnieje dokładnie 5: ((())), (()()), (())(), ()(()), ()()(). Ścieżka Dycka to ścieżka na siatce od punktu (0,0) do (2n,0) zbudowana z kroków w górę o długości (1,1) i kroków w dół o długości (1,-1), która nigdy nie opada poniżej osi x, a jest ona bezpośrednio sprzężona ze ciągiem zbalansowanych nawiasów — krok w górę oznacza otwarte nawias, a krok w dół zamknięte nawias, więc "nigdy poniżej osi" oznacza dokładnie "nigdy więcej zamkniętych niż otwartych do tej pory."

Drzewa binarne

C(n) jest również liczbą drzew binarnych pełnych o rozróżnialnej strukturze, posiadających n wewnętrznych węzłów, co odpowiada n+1 liściom. Każde takie drzewo dzieli się na poddrzewo lewe i prawe w korzeniu, a jeśli poddrzewo lewe ma i wewnętrznych węzłów, to poddrzewo prawe musi mieć n-i, co jest dokładnie rekurencją konwolucyjną zastosowaną do drzew zamiast nawiasów.

Poligonowe triangulacje i nieprzecinające się łuków

Liczba sposobów na triangulację wypukłego wielokąta o n+2 bokach przy użyciu jedynie nieprzecinających się przekątnych jest również C(n). Była to oryginalna, z 18 wieku, zagadka Eulera – on wyznaczył wzorzec dla małych wielokątów przed formalizacją sekwencji w XIX wieku przez Eugena Catalana, którego imieniem ta sekwencja obecnie nosi. Blisko powiązana jest również konstrukcja nieprzecinających się łuków: liczba sposobów na połączenie 2n punktów rozmieszczonych okręgu n przekątnymi tak, aby żadna z przekątnych się nie przecinała, wynosi również dokładnie C(n), a także ona rozkłada się w jednym wyznaczonym punkcie na dwa mniejsze problemy nieprzecinające się, dając tym samym ponownie tę samą rekurencję.

Jak szybko rośnie sekwencja

Wraz ze wzrostem n, C(n) jest asymptotycznie równe 4 podniesionemu do potęgi n, podzielonemu przez n podniesione do potęgi 1.5 i przez pierwiastek z pi. W rezultacie stosunek między kolejnymi wyrazami, C(n+1) podzielony przez C(n), stale zbliża się do 4, nie osiągając go jednak dokładnie — stosunek C(6)/C(5) wynosi 132/42, czyli około 3.14, a późniejsze stosunki stopniowo przybliżają się do 4, pozostając zawsze nieco poniżej niego, i osiągają dokładnie 4 w granicy, gdy n dąży do nieskończoności.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.