Liczby Catalana

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ść Jána Andreja Segnera (1704–1777), matematyka pochodzącego z Karpat Niemieckich.

Każdy n-ty wyraz ciągu określony jest wzorem jawnym: $c_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}\text{ dla }n⩾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}+\dots +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=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})\text{ dla }n⩾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\text{i}{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 \frac{4^n}{n^{\frac{3}{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⩾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 nieprzecinających się wewnątrz wielokąta przekątnych (zob. triangulacja).

Dowód wzoru jawnego

Dowód wzoru $c_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}\text{ dla }n⩾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{array}{c}{c}_3=c_0\cdot c_2+c_1\cdot c_1+c_2\cdot c_0\\ ⋮\\ c_n=c_0\cdot c_{n-1}+c_1\cdot c_{n-2}+\dots +c_{n-2}\cdot c_1+c_{n-1}\cdot c_0=\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i}\end{array}.$

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+\dots$ będzie funkcją tworzącą tego ciągu. Wówczas:

$\begin{array}{cc}C(x)& =c_0+c_1\cdot x+c_2\cdot x^2+\dots \\ & =1+x[c_1+c_2\cdot x+c_3\cdot x^2+\dots ]\\ & =1+x[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+\dots ]\\ & =1+x\cdot C(x)\cdot C(x)\\ & =1+x\cdot C(x{)}^2,\end{array}$

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)=\frac{1\pm \sqrt{1-4x}}{2x}.$

Ponieważ

$\underset{x\to 0}{\lim }\frac{1+\sqrt{1-4x}}{2x}=\mathrm{\infty },\underset{x\to 0}{\lim }\frac{1-\sqrt{1-4x}}{2x}=c_0=1,$

to 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

$\begin{array}{cc}c(x)& =\frac{1-\sqrt{1-4x}}{2x}\\ & =\frac{1-\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n})(-4x{)}^n}{2x}\\ & =\frac{1-1-\sum _{n=1}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n})(-4x{)}^n}{2x}\\ & =-\sum _{n=1}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n})(-4x{)}^n(2x{)}^{-1}\\ & =\sum _{n=1}^{\mathrm{\infty }}\frac{1}{2}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n})4^n{x}^{n-1}(-1{)}^{n-1}\end{array}$

Po zmianie granic sumowania otrzymujemy

$\sum _{n=0}^{\mathrm{\infty }}\frac{1}{2}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{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;

$\begin{array}{cc}{c}_n& =\frac{1}{2}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n+1})4^{n+1}(-1{)}^n\\ & =4\cdot \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\cdot 3\cdot \dots \cdot (2n-1)\cdot n!}{n!n!}{2}^n\\ & =\frac{1}{n+1}\frac{1\cdot 3\cdot \dots \cdot (2n-1)\cdot 2\cdot 4\cdot 6\cdot \dots \cdot 2n}{n!n!}\\ & =\frac{1}{n+1}\frac{(2n)!}{n!n!}\\ & =\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})\end{array}$

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ówSzablon:Fakt.

Linki zewnętrzne

• Szablon:Pismo Delta
• (pol.) Liczby Catalana w skrypcie z matematyki dyskretnej
• Szablon:MathWorld
• (ang.) Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana