Liczby Catalana

Z Wikipedii

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ń

Ten szablon: pokaż • dyskusja • edytuj

Liczby Catalana – szczególny ciąg liczbowy, mający zastosowanie w różnych aspektach kombinatoryki. Nazwane zostały na cześć belgijskiego matematyka Eugène Charles'a 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\ge 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$

Początkowe wartości ciągu, poczynając od zera, 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, \ldots$

[edytuj] Własności

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

$C_n = {2n \choose n} - {2n \choose n-1} \quad\mbox{ dla }n \ge 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}$

[edytuj] Znaczenia kombinatoryczne

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

[edytuj] 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,2 n)$ 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.

[edytuj] 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$ .

[edytuj] Liczba drzew binarnych

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

[edytuj] 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 \ge f(k), k \in {1, 2, \dots, n}$

[edytuj] 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.

[edytuj] 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 \ge 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,2 n)$ 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} \choose n}4^n x^{n-1} (-1)^{n-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}$

[edytuj] 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 Charles'a Catalana, który rozważał je jako liczbę sposobów rozmieszczeń nawiasów.

[edytuj] Linki zewnętrzne

Kategorie: Kombinatoryka • Ciągi

We provide Linux to the World

Liczby Catalana

Z Wikipedii

Spis treści

[edytuj] Własności

[edytuj] Znaczenia kombinatoryczne

[edytuj] Liczba dróg

[edytuj] Liczba rozmieszczeń nawiasów

[edytuj] Liczba drzew binarnych

[edytuj] Liczba monotonicznych dróg

[edytuj] Liczba podziałów na trójkąty

[edytuj] Dowód wzoru jawnego

[edytuj] Historia

[edytuj] Linki zewnętrzne

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach