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}={1 \over n+1}{2n \choose n}={(2n)! \over (n+1)!\,n!}\qquad {\mbox{ dla }}n\geqslant 0.$$c_{n}={1 \over n+1}{2n \choose n}={(2n)! \over (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}$$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$$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}$$C_{0}=1\quad {\mbox{i}}\quad C_{{n+1}}={\frac {2(2n+1)}{n+2}}C_{n}$,

Przybliżenie wartości $n$$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 }}}$$C_{n}\approx {4^{n} \over n^{{3 \over 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)$$(0,2n)$ dla każdego $n=0,1,2,\dots$$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)$$(x,y)$ i końcu w punkcie $(x+1,y+1)$$(x+1,y+1)$ lub $(x-1,y+1)$$(x-1,y+1)$ (gdzie $x,y\in \mathbb {N}$$x,y\in {\mathbb N}$), to ich liczba będzie wyrażona $n$$n$-tą liczba Catalana.

Liczba rozmieszczeń nawiasów

Poprzez $\star$$\star$ rozumiemy pewne działanie dwuargumentowe. Dla $n$$n$-argumentów liczba $c_{n-1}$$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}$$x_{1},x_{2},x_{3}$ otrzymać można $(x_{1}\star x_{2})\star x_{3}$$(x_{1}\star x_{2})\star x_{3}$ lub $x_{1}\star (x_{2}\star x_{3})$$x_{1}\star (x_{2}\star x_{3})$, co odpowiada $c_{3-1}=c_{2}=2$$c_{{3-1}}=c_{2}=2$.

Liczba drzew binarnych

$c_{n}$$c_{n}$ jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o $n+1$$n+1$ liściach.

Liczba monotonicznych dróg

Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie $n\times n$$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$$n$-tą liczbą Catalana. Odpowiada to liczbie monotonicznych funkcji $f$$f$ z ${1,2,\dots ,n}$${1,2,\dots ,n}$ w ${1,2,\dots ,n}$${1,2,\dots ,n}$ takich, by $k\geqslant f(k),k\in {1,2,\dots ,n}$$k\geqslant f(k),k\in {1,2,\dots ,n}$

Liczba podziałów na trójkąty

Liczba $c_{n}$$c_{n}$ wyraża liczbę sposobów podziału wielokąta wypukłego, mającego $n+2$$n+2$ krawędzie, na różne trójkąty przy pomocy przekątnych.

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\geqslant 0.$$c_{n}={1 \over n+1}{2n \choose n}={(2n)! \over (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)$$(0,0)$ do $(0,2n)$$(0,2n)$ i przy założeniu $c_{0}=1$$c_{0}=1$ otrzymamy:

$c_{1}=1$$c_{1}=1$ – bowiem do punktu $(0,2)$$(0,2)$ prowadzi jedna tylko droga,

$c_{2}=2=c_{0}\cdot c_{1}+c_{1}\cdot c_{0}$$c_{2}=2=c_{0}\cdot c_{1}+c_{1}\cdot c_{0}$ – ponieważ do punktu $(0,2)$$(0,2)$ prowadzi jedna droga $c_{1}$$c_{1}$, zaś z tego punktu do $(0,4)$$(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)$$(1,1)$ stał się środkiem nowego układu współrzędnych – wówczas do punktu $(1,3)$$(1,3)$ prowadzi tyle samo dróg, co z punktu $(0,0)$$(0,0)$ do $(0,2)$$(0,2)$, zaś z $(1,3)$$(1,3)$ wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu $(0,4)$$(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}}$${\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$$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]=$$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\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}$$=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}$$C(x)=1+x\cdot C(x)^{2}$

$x\cdot C(x)^{2}-C(x)+1=0$$x\cdot C(x)^{2}-C(x)+1=0$

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

$c(x)={1\pm {\sqrt {1-4x}} \over 2x}$$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$$\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}$$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}}=$$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}}{{\tfrac {1}{2}} \choose n}4^{n}x^{n-1}(-1)^{n-1}$$=-\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}}$.

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}$$\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$$n$-ty wyraz ciągu jest równy współczynnikowi przy $n$$n$-tej potędze $x$$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}=$$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-{\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}$$={\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}$

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