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:
Rekurencyjnie ciąg jest określony w następujący sposób:
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,...
Liczby Catalana spełniają zależność:

W sposób oczywisty pokazuje to, iż każda liczba Catalana jest liczbą naturalną. Inną postacią wzoru rekurencyjnego (tym razem pierwszego stopnia) jest:

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

Liczby Catalana posiadają wiele różnych interpretacji kombinatorycznych. Podane niżej stanowią jedynie przykłady zastosowań:
Jeżeli rozważymy wszystkie łamane, zaczynające się w początku kartezjańskiego układu współrzędnych i kończące w
dla każdego
położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku
i końcu w punkcie
lub
(gdzie
), to ich liczba będzie wyrażona
-tą liczba Catalana.
Liczba rozmieszczeń nawiasów[edytuj | edytuj kod]
Poprzez
rozumiemy pewne działanie dwuargumentowe. Dla
-argumentów liczba
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
otrzymać można
lub
co odpowiada
jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o
liściach.
Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie
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
-tą liczbą Catalana. Odpowiada to liczbie monotonicznych funkcji
z
w
takich, by
Liczba podziałów na trójkąty[edytuj | edytuj kod]
Liczba
wyraża liczbę sposobów podziału wielokąta wypukłego, mającego
krawędzie, na różne trójkąty przy pomocy nieprzecinających się wewnątrz wielokąta przekątnych (zob. triangulacja).
Dowód wzoru
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
do
i przy założeniu
otrzymamy:
– bowiem do punktu
prowadzi jedna tylko droga,
– ponieważ do punktu
prowadzi jedna droga
zaś z tego punktu do
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
stał się środkiem nowego układu współrzędnych – wówczas do punktu
prowadzi tyle samo dróg, co z punktu
do
zaś z
wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu
Postępując dalej analogicznie, otrzymamy:

Aby otrzymać wzór jawny, którym określony jest ciąg, można użyć techniki funkcji tworzących ciągu.
Niech
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de4a02fa0178293ebd7b528116ad06e5f43c5739)
co wynika z definicji operacji mnożenia funkcji tworzących. Mamy więc


Rozwiązując to równanie, po przyjęciu za szukaną zmienną
otrzymujemy:

Ponieważ

to rozpatrujemy jedynie pierwiastek
Korzystając z uogólnionego na liczby rzeczywiste symbolu Newtona oraz jego własności okazuje się, że

Po zmianie granic sumowania otrzymujemy

Z własności funkcji tworzących wiemy, że
-ty wyraz ciągu jest równy współczynnikowi przy
-tej potędze
czyli;

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.
- ↑ Ronald Graham, Donald Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 233.