Liczby Catalana

rekurencyjny ciąg liczbowy

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,...

Własności

edytuj

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ć:

 

Znaczenia kombinatoryczne

edytuj

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

Liczba dróg

edytuj

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

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

edytuj

  jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o   liściach.

Liczba monotonicznych dróg

edytuj

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

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

edytuj

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

edytuj

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[potrzebny przypis].

Przypisy

edytuj
  1. Ronald Graham, Donald Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 233.

Linki zewnętrzne

edytuj