Liczby Catalana: Zastosowania liczb Catalana

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

Subskrybuj: Posty (Atom)