Liczby Catalana

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

permutacja bez powtórzeń permutacja z powtórzeniami 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ść 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}}{2n \choose n}={\frac {(2n)!}{(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 {\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\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 nieprzecinających się wewnątrz wielokąta przekątnych.

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\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:

${\begin{aligned}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{aligned}}$

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ż

$\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,$

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{aligned}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{aligned}}$

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;

${\begin{aligned}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{aligned}}$

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