Liczby Catalana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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 (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 | 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]