Liczby Catalana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja


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ść matematyka pochodzącego z Karpat Niemieckich, Jána Andreja Segnera (1704-1777).

Każdy n-ty wyraz ciągu określony jest wzorem jawnym: c_n = {1 \over n+1}{2n \choose n} = {(2n)! \over (n+1)!\,n!} \qquad\mbox{ dla }n\geqslant 0.

Rekurencyjnie ciąg jest określony w następujący sposób: c_0 = 1; c_n = c_0 \cdot c_{n-1} + c_1 \cdot c_{n-2} + \ldots + c_{n-2} \cdot c_1 + c_{n-1} \cdot c_0 = \sum_{i=0}^{n-1} c_{i} \cdot c_{n-1-i}

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

C_n = {2n \choose n} - {2n \choose n+1} \quad\mbox{ dla }n \geqslant 1.

W sposób oczywisty pokazuje to, iż każda liczba Catalana jest liczbą naturalną. Inną postacią wzoru rekurencyjnego (tym razem pierwszego stopnia) jest:

C_0 = 1 \quad \mbox{i} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

Przybliżenie wartości n-tej liczby Catalana jest możliwe dzięki wzorowi Stirlinga na wartość silni i ma postać:

C_n \approx {4^n \over n^{3 \over 2}\sqrt\pi}

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 (0,2n) dla każdego n=0, 1, 2, \dots, położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku (x, y) i końcu w punkcie (x+1, y+1) lub (x-1, y+1) (gdzie x, y \in \mathbb N), to ich liczba będzie wyrażona n-tą liczba Catalana.

Liczba rozmieszczeń nawiasów[edytuj | edytuj kod]

Poprzez \star rozumiemy pewne działanie dwuargumentowe. Dla n-argumentów liczba c_{n-1} 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 x_1, x_2, x_3 otrzymać można (x_1 \star x_2) \star x_3 lub x_1 \star (x_2 \star x_3), co odpowiada c_{3-1}=c_2=2.

Liczba drzew binarnych[edytuj | edytuj kod]

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

Liczba monotonicznych dróg[edytuj | edytuj kod]

Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie n \times n 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 n-tą liczbą Catalana. Odpowiada to liczbie monotonicznych funkcji f z {1, 2, \dots, n} w {1, 2, \dots, n} takich, by k \geqslant f(k), k \in {1, 2, \dots, n}

Catalan number 4x4 grid example.svg

Liczba podziałów na trójkąty[edytuj | edytuj kod]

Liczba c_n wyraża liczbę sposobów podziału wielokąta wypukłego, mającego n+2 krawędzie, na różne trójkąty przy pomocy przekątnych.

Dowód wzoru jawnego[edytuj | edytuj kod]

Dowód wzoru c_n = {1 \over n+1}{2n \choose n} = {(2n)! \over (n+1)!\,n!} \qquad\mbox{ dla }n \geqslant 0. 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 (0, 0) do (0, 2n) i przy założeniu c_0=1 otrzymamy:

c_1=1 – bowiem do punktu (0, 2) prowadzi jedna tylko droga,
c_2=2 = c_0 \cdot c_1 + c_1 \cdot c_0 – ponieważ do punktu (0, 2) prowadzi jedna droga c_1, zaś z tego punktu do (0, 4) 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 (1, 1) stał się środkiem nowego układu współrzędnych – wówczas do punktu (1, 3) prowadzi tyle samo dróg, co z punktu (0, 0) do (0, 2), zaś z (1, 3) wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu (0, 4).

Postępując dalej analogicznie, otrzymamy:

\begin{cases} c_3 = c_0 \cdot c_2 + c_1 \cdot c_1 + c_2 \cdot c_0 \\ \vdots \\ c_n = c_0 \cdot c_{n-1} + c_1 \cdot c_{n-2} + \ldots + c_{n-2} \cdot c_1 + c_{n-1} \cdot c_0 = \sum_{i=0}^{n-1}\; C_i\,C_{n-1-i}\end{cases}.

Aby otrzymać wzór jawny, którym określony jest ciąg, można użyć techniki funkcji tworzących ciągu.

Niech C(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \ldots będzie funkcją tworzącą tego ciągu. Wówczas:

C(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \ldots = 1 + x\left[c_1 + c_2 \cdot x + c_3 \cdot x^2 + \dots\right] =
=1 + x\left[c_0 \cdot c_0 + (c_0 \cdot c_1 + c_1 \cdot c_0)x + (c_0 \cdot c_2 + c_1 \cdot c_1 + c_2 \cdot c_0)x^2 + \ldots\right] =
= 1 + x \cdot C(x) \cdot C(x) = 1 + x \cdot C(x)^2,

co wynika z definicji operacji mnożenia funkcji tworzących. Mamy więc

C(x) = 1 + x \cdot C(x)^2
x \cdot C(x)^2 - C(x) +1 = 0

Rozwiązując to równanie, po przyjęciu za szukaną zmienną C(x) otrzymujemy:

c(x) = {1 \pm \sqrt{1-4x} \over 2x}

Ponieważ

\lim_{x \to 0}\;{1 + \sqrt{1-4x} \over 2x} = \infty, \lim_{x \to 0}\;{1 - \sqrt{1-4x} \over 2x} = c_0 = 1,

to rozpatrujemy jedynie pierwiastek c(x) = {1 - \sqrt{1-4x} \over 2x}.

Korzystając z uogólnionego na liczby rzeczywiste symbolu Newtona oraz jego własności okazuje się, że

c(x) = {1 - \sqrt{1-4x} \over 2x} = \frac{1 - \sum_{n=0}^\infty {\tfrac{1}{2} \choose n} (-4x)^n}{2x} = \frac{1 - 1 - \sum_{n=1}^\infty {\tfrac{1}{2} \choose n} (-4x)^n}{2x} =
=-\sum_{n=1}^{\infty} {\tfrac{1}{2} \choose n} (-4x)^n (2x)^{-1} = \sum_{n=1}^\infty \tfrac{1}{2}{\tfrac{1}{2} \choose n}4^n x^{n-1}(-1)^{n-1}.

Po zmianie granic sumowania otrzymujemy

\sum_{n=0}^\infty \frac{1}{2}{\tfrac{1}{2} \choose n+1}4^{n+1} (-1)^n x^n.

Z własności funkcji tworzących wiemy, że n-ty wyraz ciągu jest równy współczynnikowi przy n-tej potędze x, czyli;


c_n = \frac{1}{2} {\tfrac{1}{2} \choose n+1} 4^{n+1} (-1)^n =
      4\cdot\frac{1}{2} \frac{\tfrac{1}{2}(\tfrac{1}{2}-1)(\tfrac{1}{2}-2) \ldots (\tfrac{1}{2}-n)}{(n+1)!}(-1)^n 4^{n}=

    = \frac{1}{n+1}\frac{(1-\tfrac{1}{2})(2-\tfrac{1}{2})\ldots(n-\tfrac{1}{2})}{n!} 2^n 2^n =
      \frac{1}{n+1}\frac{1 \cdot 3 \cdot \ldots \cdot (2n-1) \cdot n!}{n!n!} 2^n =

    = \frac{1}{n+1}\frac{1 \cdot 3 \cdot \ldots \cdot (2n-1) \cdot 2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{n!n!} =
      {1 \over n+1} {(2n)! \over n!n!} = {1 \over n+1} {2n \choose n}

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

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

Linki zewnętrzne[edytuj | edytuj kod]