Liczby Catalana

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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 = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(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*c_{n-1} + c_1*c_{n-2} + \dots + c_{n-2}*c_1 + c_{n-1}*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, …

[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ść silnii, i ma postać:

$C_n \sim \frac{4^n}{n^{3/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 z (0,0) do (0,2n)

Jeżeli rozważymy wszystkie łamane, zaczynające się w punkcie (0,0) 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) (x, y - naturalne), to ich liczba będzie wyrażona n-tą liczba Catalana.

[edytuj] Liczba rozmieszczeń nawiasów

Poprzez $*$ 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 3 argumentów $x 1, x 2, x 3$ otrzymać można $(x 1 * x 2) * x 3$ lub $x 1 * (x 2 * x 3)$ , co odpowiada $c 3 - 1 = c 2 = 2$ .

[edytuj] Liczba monotonicznych dróg

Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie $n x 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 $\lbrace 1, 2, \dots, n \rbrace$ w $\lbrace 1, 2, \dots, n \rbrace$ takich, by $k \ge f(k), k \in \lbrace 1, 2, \dots, n \rbrace$

[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 = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(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, 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 * c 1 + c 1 * c 0$ - ponieważ do punktu (0, 2) prowadzi 1 droga $c 1$ , zaś z tego punktu do (0, 4) można przejść zgodnie z założonymi możliwościamo wyboru kolejnego odcinka składowego na 1 sposób; rozważmy teraz pewne przesunięcie układu współrzędnych tak, by punkt (1, 1) stał się "nowy" środkiem 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 1 sposób do punktu (0, 4)

Postępując dalej analogicznie, otrzymamy:

$c 3 = c 0 * c 2 + c 1 * c 1 + c 2 * c 0$

$\vdots$

$c_n=c_0*c_{n-1} + c_1*c_{n-2} + \dots + c_{n-2}*c_1 + c_{n-1}*c_0 =\sum_{i=0}^{n-1}C_i\,C_{n-1-i}$

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*x + c_2*x^2 + \dots$ będzie funkcją tworzącą tego ciagu. Wówczas:

$C(x) = c_0 + c_1*x + c_2*x^2 + \dots = 1 + x[c_1 + c_2*x + c_3*x^2 + \dots] =$

$=1 + x[c_0*c_0 + (c_0*c_1 + c_1*c_0)x + (c_0*c_2 + c_1*c_1 + c_2*c_0)x^2 + \dots = 1 + x*C(x)*C(x) = 1 + x*C(x)^2$ , co wynika z definicji operacji mnożenia funkcji tworzących. Wynika stąd:

$C (x) = 1 + x * C (x) 2$

$x * C (x) 2 - C (x) + 1 = 0$

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

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

Ponieważ $lim_{x \to 0} \frac{1 + \sqrt{1-4x}}{2x} = \infty, lim_{x \to 0} \frac{1 - \sqrt{1-4x}}{2x} = c_0 = 1$ rozpatrujemy jedynie pierwiastek $c(x) = \frac{1 - \sqrt{1-4x}}{2x}$ .

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

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

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

Po zmianie granic sumowania:

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

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

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

$= \frac{1}{n+1}\frac{(1-\frac{1}{2})(2-\frac{1}{2})\dots(n-\frac{1}{2})}{n!} 2^n 2^n = \frac{1}{n+1}\frac{1*3*\dots*(2n-1)*n!}{n!n!} 2^n = \frac{1}{n+1} \frac{2n!}{n!n!} =$

$= \frac{1}{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 Charlesa Catalana, który rozważał je jako liczbę sposobów rozmieszczeń nawiasów.

[edytuj] Linki zewnętrzne

Źródło: "http://pl.wikipedia.org../../../l/i/c/Liczby_Catalana_ee52.html"

Kategorie: Kombinatoryka • Liczby

Liczby Catalana

Z Wikipedii

Spis treści

[edytuj] Własności

[edytuj] Znaczenia kombinatoryczne

[edytuj] Liczba dróg z (0,0) do (0,2n)

[edytuj] Liczba rozmieszczeń nawiasów

[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

techniczne

zmiany

Szukaj

W innych językach