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
dla każdego
, położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku
i końcu w punkcie
lub
(gdzie
), to ich liczba będzie wyrażona
-tą liczba Catalana.
Liczba rozmieszczeń nawiasów
Poprzez
rozumiemy pewne działanie dwuargumentowe. Dla
-argumentów liczba
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
otrzymać można
lub
, co odpowiada
.
Liczba drzew binarnych
jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o
liściach.
Liczba monotonicznych dróg
Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie
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
-tą liczbą Catalana. Odpowiada to liczbiemonotonicznych funkcji
z
w
takich, by

Brak komentarzy:
Prześlij komentarz