Liczby Catalana

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


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 (18141894)[1]. Bywają również nazywane liczbami Segnera, na cześć Jána Andreja Segnera (17041777), 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 | edytuj kod]

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 | edytuj kod]

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

Liczba dróg[edytuj | edytuj kod]

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

Liczba drzew binarnych[edytuj | edytuj kod]

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

Liczba monotonicznych dróg[edytuj | edytuj kod]

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

Catalan number 4x4 grid example.svg

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.

Dowód wzoru jawnego[edytuj | edytuj kod]

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 | edytuj kod]

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[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]