Tekst źródłowy strony Liczby Catalana

'''Liczby Catalana''' – szczególny [[Ciąg (matematyka)|ciąg liczbowy]], mający zastosowanie w różnych aspektach [[Kombinatoryka|kombinatoryki]]. Nazwane zostały na cześć [[Belgia|belgijskiego]] matematyka [[Eugène Charles Catalan|Eugène Charlesa Catalana]] (1814–1894)<ref>{{cytuj książkę |nazwisko = Graham |imię = Ronald |nazwisko2 = Knuth |imię2 = Donald |nazwisko3 = Patashnik |imię3 = Oren |tytuł = Matematyka konkretna |rok = 2006 |wydawca = PWN |miejsce = Warszawa|strony=233}}</ref>. Bywają również nazywane ''liczbami Segnera'', na cześć [[Johann Andreas von Segner|Jána Andreja Segnera]] (1704–1777), matematyka pochodzącego z [[Karpaty|Karpat]] [[Niemcy|Niemieckich]].

Każdy n-ty wyraz ciągu określony jest [[wzór jawny|wzorem jawnym]]: <math>c_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ dla }n\geqslant 0.</math>

[[rekurencja|Rekurencyjnie]] ciąg jest określony w następujący sposób: <math>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}.</math>

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

[[1 (liczba)|1]], [[1 (liczba)|1]], [[2 (liczba)|2]], [[5 (liczba)|5]], [[14 (liczba)|14]], [[42 (liczba)|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ść:
: <math>C_n = {2n \choose n} - {2n \choose n+1} \quad\mbox{ dla }n \geqslant 1.</math>

W sposób oczywisty pokazuje to, iż każda liczba Catalana jest [[Liczby naturalne|liczbą naturalną]]. Inną postacią wzoru rekurencyjnego (tym razem pierwszego stopnia) jest:
: <math>C_0 = 1 \quad \mbox{i} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,</math>

Przybliżenie wartości <math>n</math>-tej liczby Catalana jest możliwe dzięki [[Wzór Stirlinga|wzorowi Stirlinga]] na wartość [[Silnia|silni]] i ma postać:
: <math>C_n \approx \frac{4^n}{n^\frac{3}{2}\sqrt\pi}</math>

== 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 [[Układ współrzędnych kartezjańskich|kartezjańskiego układu współrzędnych]] i kończące w <math>(0,2n)</math> dla każdego <math>n=0, 1, 2, \dots,</math> położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku <math>(x, y)</math> i końcu w punkcie <math>(x+1, y+1)</math> lub <math>(x-1, y+1)</math> (gdzie <math>x, y \in \mathbb N</math>), to ich liczba będzie wyrażona <math>n</math>-tą liczba Catalana.

=== Liczba rozmieszczeń nawiasów ===
Poprzez <math>\star</math> rozumiemy pewne [[działanie dwuargumentowe]]. Dla <math>n</math>-argumentów liczba <math>c_{n-1}</math> wyraża liczbę sposobów, na które można rozmieścić nawiasy w takim wyrażeniu, czyli – dla działania [[Łączność (matematyka)|niełącznego]] – maksymalną liczbę wyników, które można uzyskać. Przykładowo, dla trzech argumentów <math>x_1, x_2, x_3</math> otrzymać można <math>(x_1 \star x_2) \star x_3</math> lub <math>x_1 \star (x_2 \star x_3),</math> co odpowiada <math>c_{3-1}=c_2=2.</math>

=== Liczba drzew binarnych ===
<math>c_n</math> jest równa liczbie różnych ukorzenionych regularnych [[drzewo binarne|drzew binarnych]] o <math>n+1</math> [[Liść (informatyka)|liściach]].

=== Liczba monotonicznych dróg ===
Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie <math>n \times n</math> z dolnego lewego wierzchołka do górnego prawego, tak, by nigdy nie przekroczyć przekątnej łączącej te wierzchołki i były [[Funkcja monotoniczna|monotoniczne]], łatwo jest zauważyć, że wyrażają się one <math>n</math>-tą liczbą Catalana. Odpowiada to liczbie [[funkcja monotoniczna|monotonicznych funkcji]] <math>f</math> z <math>1, 2, \dots, n</math> w <math>1, 2, \dots, n</math> takich, by <math>k \geqslant f(k), k \in {1, 2, \dots, n}</math>
[[Plik:Catalan number 4x4 grid example.svg|center|450px]]

=== Liczba podziałów na trójkąty ===
Liczba <math>c_n</math> wyraża liczbę sposobów podziału wielokąta wypukłego, mającego <math>n+2</math> krawędzie, na różne trójkąty przy pomocy nieprzecinających się wewnątrz wielokąta przekątnych (zob. [[Triangulacja (grafika komputerowa)|triangulacja]]).

== Dowód wzoru jawnego ==
Dowód wzoru <math>c_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ dla }n \geqslant 0.</math> 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 <math>(0, 0)</math> do <math>(0, 2n)</math> i przy założeniu <math>c_0=1</math> otrzymamy:
: <math>c_1=1</math> – bowiem do punktu <math>(0, 2)</math> prowadzi jedna tylko droga,
: <math>c_2=2 = c_0 \cdot c_1 + c_1 \cdot c_0</math> – ponieważ do punktu <math>(0, 2)</math> prowadzi jedna droga <math>c_1,</math> zaś z tego punktu do <math>(0, 4)</math> 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 <math>(1, 1)</math> stał się środkiem nowego układu współrzędnych – wówczas do punktu <math>(1, 3)</math> prowadzi tyle samo dróg, co z punktu <math>(0, 0)</math> do <math>(0, 2),</math> zaś z <math>(1, 3)</math> wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu <math>(0, 4).</math>

Postępując dalej analogicznie, otrzymamy:
: <math>\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}.</math>

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

Niech <math>C(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \ldots</math> będzie funkcją tworzącą tego ciągu. Wówczas:
: <math>\begin{align}
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,
\end{align}</math>

co wynika z definicji operacji [[Mnożenie|mnożenia]] funkcji tworzących. Mamy więc
: <math>C(x) = 1 + x \cdot C(x)^2,</math>
: <math>x \cdot C(x)^2 - C(x) +1 = 0.</math>

Rozwiązując to równanie, po przyjęciu za szukaną zmienną <math>C(x)</math> otrzymujemy:
: <math>c(x) = \frac{1 \pm \sqrt{1-4x}}{2x}.</math>

Ponieważ
: <math>\lim_{x \to 0}\;\frac{1 + \sqrt{1-4x}}{2x} = \infty, \quad \lim_{x \to 0}\;\frac{1 - \sqrt{1-4x}}{2x} = c_0 = 1,</math>

to rozpatrujemy jedynie pierwiastek <math>c(x) = \frac{1 - \sqrt{1-4x}}{2x}.</math>

Korzystając z uogólnionego na liczby rzeczywiste [[symbol Newtona|symbolu Newtona]] oraz jego własności okazuje się, że
: <math>\begin{align}
c(x) &= \frac{1 - \sqrt{1-4x}}{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}
\end{align}</math>

Po zmianie granic sumowania otrzymujemy
: <math>\sum_{n=0}^\infty \frac{1}{2}{\tfrac{1}{2} \choose n+1}4^{n+1} (-1)^n x^n.</math>

Z własności funkcji tworzących wiemy, że <math>n</math>-ty wyraz ciągu jest równy współczynnikowi przy <math>n</math>-tej potędze <math>x,</math> czyli;
: <math>\begin{align}
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!} \\
&= \frac{1}{n+1} \frac{(2n)!}{n!n!} \\
&= \frac{1}{n+1} {2n \choose n}
\end{align}</math>

== Historia ==
Liczby te zostały po raz pierwszy wprowadzone przez [[Leonhard Euler|Leonarda Eulera]] w XVIII wieku, który badał liczbę podziałów [[wielokąt]]ów na [[trójkąt]]y. Zostały nazwane na cześć Eugène Charlesa Catalana, który rozważał je jako liczbę sposobów rozmieszczeń [[nawias]]ów{{fakt|data=2024-06}}.

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{Pismo Delta | url = 1996/11/liczby-catalana/ | autor = Włodzimierz Bieliński, Krzysztof Parol | tytuł = Liczby Catalana | data = listopad 1996 | data dostępu = 2024-11-02 }}
* (pol.) [http://wazniak.mimuw.edu.pl/index.php/Matematyka_dyskretna_1/Wyk%C5%82ad_8:_Funkcje_tworz%C4%85ce_w_zliczaniu_obiekt%C3%B3w_kombinatorycznych#Zliczanie_drzew Liczby Catalana w skrypcie z matematyki dyskretnej]
* {{MathWorld|adres=CatalanNumber |tytuł=Catalan Number |data dostępu=12 grudnia 2020}}
* (ang.) [http://www-math.mit.edu/~rstan/ec/catadd.pdf Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana]

{{Kombinatoryka}}
{{Typy liczb naturalnych}}

{{Kontrola autorytatywna}}

[[Kategoria:Kombinatoryka]]
[[Kategoria:Rodzaje liczb naturalnych|C]]