Zastosowania liczb Catalana


Liczba dróg

Jeżeli rozważymy wszystkie łamane, zaczynające się w początku kartezjańskiego układu współrzędnych i kończące w (0,2n) dla każdego n=0, 1, 2, \dots, położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku (x, y) i końcu w punkcie (x+1, y+1) lub (x-1, y+1) (gdzie x, y \in \mathbb N), to ich liczba będzie wyrażona n-tą liczba Catalana.

Liczba rozmieszczeń nawiasów

Poprzez \star rozumiemy pewne działanie dwuargumentowe. Dla n-argumentów liczba c_{n-1} wyraża liczbę sposobów, na które można rozmieścić nawiasy w takim wyrażeniu, czyli - dla działania niełącznego - maksymalną liczbę wyników, które można uzyskać. Przykładowo, dla trzech argumentów x_1, x_2, x_3 otrzymać można (x_1 \star x_2) \star x_3 lub x_1 \star (x_2 \star x_3), co odpowiada c_{3-1}=c_2=2.

Liczba drzew binarnych

c_n jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o n+1 liściach.

Liczba monotonicznych dróg

Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie n \times n z dolnego lewego wierzchołka do górnego prawego, tak, by nigdy nie przekroczyć przekątnej łączącej te wierzchołki i były monotoniczne, łatwo jest zauważyć, że wyrażają się one n-tą liczbą Catalana. Odpowiada to liczbiemonotonicznych funkcji f z {1, 2, \dots, n} w {1, 2, \dots, n} takich, by 

k \geqslant f(k), k \in {1, 2, \dots, n}



Brak komentarzy:

Prześlij komentarz