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)^[1]. 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: ${\displaystyle 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: ${\displaystyle 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ść:

${\displaystyle 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:

${\displaystyle C_{0}=1\quad {\mbox{i}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}$

Przybliżenie wartości ${\displaystyle n}$-tej liczby Catalana jest możliwe dzięki wzorowi Stirlinga na wartość silni i ma postać:

${\displaystyle 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 ${\displaystyle (0,2n)}$ dla każdego ${\displaystyle n=0,1,2,\dots ,}$ położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku ${\displaystyle (x,y)}$ i końcu w punkcie ${\displaystyle (x+1,y+1)}$ lub ${\displaystyle (x-1,y+1)}$ (gdzie ${\displaystyle x,y\in \mathbb {N} }$), to ich liczba będzie wyrażona ${\displaystyle n}$-tą liczba Catalana.

Liczba rozmieszczeń nawiasów

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

Liczba drzew binarnych

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

Liczba monotonicznych dróg

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

Liczba podziałów na trójkąty

Liczba ${\displaystyle c_{n}}$ wyraża liczbę sposobów podziału wielokąta wypukłego, mającego ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (0,0)}$ do ${\displaystyle (0,2n)}$ i przy założeniu ${\displaystyle c_{0}=1}$ otrzymamy:

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

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

Postępując dalej analogicznie, otrzymamy:

${\displaystyle {\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 ${\displaystyle C(x)=c_{0}+c_{1}\cdot x+c_{2}\cdot x^{2}+\ldots }$ będzie funkcją tworzącą tego ciągu. Wówczas:

${\displaystyle {\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

${\displaystyle C(x)=1+x\cdot C(x)^{2},}$

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

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

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

Ponieważ

${\displaystyle \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 ${\displaystyle 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

${\displaystyle {\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

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

${\displaystyle {\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.

Przypisy

Linki zewnętrzne

• (pol.) Liczby Catalana w skrypcie z matematyki dyskretnej
• Eric W.E.W. Weisstein Eric W.E.W., Catalan Number, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).
• (ang.) Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana