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]

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

Catalan number 4x4 grid example.svg

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 przekątnych.

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.

Przypisy

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

Linki zewnętrzne[edytuj]