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'a Charles'a Catalana (1814–1894)^[1]. Bywają również nazywane liczbami Segnera, na cześć Johanna Andreasa Segnera (1704–1777), niemieckiego matematyka pochodzącego z Pressburga (dziś Bratysława).

Każdy wyraz ciągu ma wzór jawny:

${\displaystyle {\begin{aligned}n&\in \mathbb {N} \Rightarrow \\c_{n}&={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}.\end{aligned}}}$

Rekurencyjnie ciąg jest określony następująco:

${\displaystyle {\begin{aligned}c_{0}&:=1,\\c_{n}&:=c_{0}c_{n-1}+c_{1}c_{n-2}+\ldots +c_{n-2}c_{1}+c_{n-1}c_{0}=\\&=\sum _{i=0}^{n-1}c_{i}c_{n-1-i}.\end{aligned}}}$

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, ... (ciąg A000108 w OEIS).

Liczby Catalana posiadają wiele różnych interpretacji kombinatorycznych. Podane niżej stanowią jedynie przykłady zastosowań:

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

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

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.

• WłodzimierzW. Bieliński WłodzimierzW., KrzysztofK. Parol KrzysztofK., Liczby Catalana, „Delta”, listopad 1996, ISSN 0137-3005 [dostęp 2024-11-02] .
• (pol.) Liczby Catalana w skrypcie z matematyki dyskretnej
• Eric W.E.W. Weisstein Eric W.E.W., Catalan Number, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• (ang.) Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana