mały|Eugène Charles Catalan (1814–1894)
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). 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:
Rekurencyjnie ciąg jest określony następująco:
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, ... .
Wzory Dokładne 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żone Wzór Stirlinga na przybliżenie silni pozwala też przybliżać liczby Catalana:
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 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 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
Liczba drzew binarnych jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o liściach.
Liczba monotonicznych dróg 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 center|450px
Liczba podziałów na trójkąty 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 jawnego 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:
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;
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
(ang.) Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana
Kategoria:Kombinatoryka C