Liczby Catalana

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja kombinacja bez powtórzeń kombinacja z powtórzeniami wariacja bez powtórzeń wariacja z powtórzeniami liczby Bella liczby Catalana liczby Stirlinga liczby Eulera zasada szufladkowa Dirichleta zasada włączeń i wyłączeń

Liczby Catalana – szczególny ciąg liczbowy, mający zastosowanie w różnych aspektach kombinatoryki. Nazwane zostały na cześć belgijskiego matematyka Eugène Charlesa Catalana (1814–1894). Bywają również nazywane liczbami Segnera, na cześć matematyka pochodzącego z Karpat Niemieckich, Jána Andreja Segnera (1704-1777).

Każdy n-ty wyraz ciągu określony jest wzorem jawnym: $c_n = {1 \over n+1}{2n \choose n} = {(2n)! \over (n+1)!\,n!} \qquad\mbox{ dla }n\geqslant 0.$

Rekurencyjnie ciąg jest określony w następujący sposób: $c_0 = 1; c_n = c_0 \cdot c_{n-1} + c_1 \cdot c_{n-2} + \ldots + c_{n-2} \cdot c_1 + c_{n-1} \cdot c_0 = \sum_{i=0}^{n-1} c_{i} \cdot c_{n-1-i}$

Początkowe wartości ciągu, poczynając od wyrazu zerowego, to:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

Własności

Liczby Catalana spełniają zależność:

$C_n = {2n \choose n} - {2n \choose n+1} \quad\mbox{ dla }n \geqslant 1$.

W sposób oczywisty pokazuje to, iż każda liczba Catalana jest liczbą naturalną. Inną postacią wzoru rekurencyjnego (tym razem pierwszego stopnia) jest:

$C_0 = 1 \quad \mbox{i} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n$,

Przybliżenie wartości $n$-tej liczby Catalana jest możliwe dzięki wzorowi Stirlinga na wartość silni i ma postać:

$C_n \approx {4^n \over n^{3 \over 2}\sqrt\pi}$

Znaczenia kombinatoryczne

Liczby Catalana posiadają wiele różnych interpretacji kombinatorycznych. Podane niżej stanowią jedynie przykłady zastosowań:

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 liczbie monotonicznych funkcji $f$ z ${1, 2, \dots, n}$ w ${1, 2, \dots, n}$ takich, by $k \geqslant f(k), k \in {1, 2, \dots, n}$

Liczba podziałów na trójkąty

Liczba $c_n$ wyraża liczbę sposobów podziału wielokąta wypukłego, mającego $n+2$ krawędzie, na różne trójkąty przy pomocy przekątnych.

Dowód wzoru jawnego

Dowód wzoru $c_n = {1 \over n+1}{2n \choose n} = {(2n)! \over (n+1)!\,n!} \qquad\mbox{ dla }n \geqslant 0.$ można otrzymać na wiele sposobów i zależnie od różnych interpretacji liczb Catalana. Przyjmując, że rozpatrujemy przypadek liczby dróg z punktu $(0, 0)$ do $(0, 2n)$ i przy założeniu $c_0=1$ otrzymamy:

$c_1=1$ – bowiem do punktu $(0, 2)$ prowadzi jedna tylko droga,

$c_2=2 = c_0 \cdot c_1 + c_1 \cdot c_0$ – ponieważ do punktu $(0, 2)$ prowadzi jedna droga $c_1$, zaś z tego punktu do $(0, 4)$ można przejść zgodnie z założonymi możliwościami wyboru kolejnego odcinka składowego na jeden sposób.

Rozważmy teraz pewne przesunięcie układu współrzędnych tak, by punkt $(1, 1)$ stał się środkiem nowego układu współrzędnych – wówczas do punktu $(1, 3)$ prowadzi tyle samo dróg, co z punktu $(0, 0)$ do $(0, 2)$, zaś z $(1, 3)$ wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu $(0, 4)$.

Postępując dalej analogicznie, otrzymamy:

$\begin{cases} c_3 = c_0 \cdot c_2 + c_1 \cdot c_1 + c_2 \cdot c_0 \\ \vdots \\ c_n = c_0 \cdot c_{n-1} + c_1 \cdot c_{n-2} + \ldots + c_{n-2} \cdot c_1 + c_{n-1} \cdot c_0 = \sum_{i=0}^{n-1}\; C_i\,C_{n-1-i}\end{cases}$.

Aby otrzymać wzór jawny, którym określony jest ciąg, można użyć techniki funkcji tworzących ciągu.

Niech $C(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \ldots$ będzie funkcją tworzącą tego ciągu. Wówczas:

$C(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \ldots = 1 + x\left[c_1 + c_2 \cdot x + c_3 \cdot x^2 + \dots\right] =$

$=1 + x\left[c_0 \cdot c_0 + (c_0 \cdot c_1 + c_1 \cdot c_0)x + (c_0 \cdot c_2 + c_1 \cdot c_1 + c_2 \cdot c_0)x^2 + \ldots\right] =$

$= 1 + x \cdot C(x) \cdot C(x) = 1 + x \cdot C(x)^2$,

co wynika z definicji operacji mnożenia funkcji tworzących. Mamy więc

$C(x) = 1 + x \cdot C(x)^2$

$x \cdot C(x)^2 - C(x) +1 = 0$

Rozwiązując to równanie, po przyjęciu za szukaną zmienną $C(x)$ otrzymujemy:

$c(x) = {1 \pm \sqrt{1-4x} \over 2x}$

Ponieważ

$\lim_{x \to 0}\;{1 + \sqrt{1-4x} \over 2x} = \infty, \lim_{x \to 0}\;{1 - \sqrt{1-4x} \over 2x} = c_0 = 1$,

to rozpatrujemy jedynie pierwiastek $c(x) = {1 - \sqrt{1-4x} \over 2x}$.

Korzystając z uogólnionego na liczby rzeczywiste symbolu Newtona oraz jego własności okazuje się, że

$c(x) = {1 - \sqrt{1-4x} \over 2x} = \frac{1 - \sum_{n=0}^\infty {\tfrac{1}{2} \choose n} (-4x)^n}{2x} = \frac{1 - 1 - \sum_{n=1}^\infty {\tfrac{1}{2} \choose n} (-4x)^n}{2x} =$

$=-\sum_{n=1}^{\infty} {\tfrac{1}{2} \choose n} (-4x)^n (2x)^{-1} = \sum_{n=1}^\infty \tfrac{1}{2}{\tfrac{1}{2} \choose n}4^n x^{n-1}(-1)^{n-1}$.

Po zmianie granic sumowania otrzymujemy

$\sum_{n=0}^\infty \frac{1}{2}{\tfrac{1}{2} \choose n+1}4^{n+1} (-1)^n x^n$.

Z własności funkcji tworzących wiemy, że $n$-ty wyraz ciągu jest równy współczynnikowi przy $n$-tej potędze $x$, czyli;

$c_n = \frac{1}{2} {\tfrac{1}{2} \choose n+1} 4^{n+1} (-1)^n = 4\cdot\frac{1}{2} \frac{\tfrac{1}{2}(\tfrac{1}{2}-1)(\tfrac{1}{2}-2) \ldots (\tfrac{1}{2}-n)}{(n+1)!}(-1)^n 4^{n}=$

$= \frac{1}{n+1}\frac{(1-\tfrac{1}{2})(2-\tfrac{1}{2})\ldots(n-\tfrac{1}{2})}{n!} 2^n 2^n = \frac{1}{n+1}\frac{1 \cdot 3 \cdot \ldots \cdot (2n-1) \cdot n!}{n!n!} 2^n =$

$= \frac{1}{n+1}\frac{1 \cdot 3 \cdot \ldots \cdot (2n-1) \cdot 2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{n!n!} = {1 \over n+1} {(2n)! \over n!n!} = {1 \over n+1} {2n \choose n}$

Historia

Liczby te zostały po raz pierwszy wprowadzone przez Leonarda Eulera w XVIII wieku, który badał liczbę podziałów wielokątów na trójkąty. Zostały nazwane na cześć Eugène Charlesa Catalana, który rozważał je jako liczbę sposobów rozmieszczeń nawiasów.

Linki zewnętrzne

• (pol.) Liczby Catalana w skrypcie z matematyki dyskretnej
• (ang.) Hasło w serwisie MathWorld
• (ang.) Stanley, R.P - dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana