Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:
Węzeł wewnętrzny drzewa binarnego jest zdefiniowany rekurencyjnie:
Liczba Catalana \( c_n \) to liczba drzew binarnych o \( n \) węzłach wewnętrznych.
Przykład
Drzewa binarne są modelem dla tzw. wyrażeń nawiasowych, czyli termów z jednym działaniem binarnym i jedną zmienną \( x \). Wyrażenia takie są zdefiniowane poprzez:
Węzły wewnętrzne wyrażenia nawiasowego, to podtermy nie będące zmiennymi.
Obserwacja 8.1
Liczby Catalana \( c_n \) spełniają zależność rekurencyjną:
\( \left \{ \begin{array} {l} {rcl} c_0 & = & 1, \\ c_n & = & c_0 c_{n-1}+c_1 c_{n-2}+\ldots+ c_{n-1} c_0,\quad\textrm{dla}\ n\geq 1. \end{array} \right . \)
Dowód
Pojedynczy wierzchołek jest jedynym pełnym drzewem binarnym bez węzłów wewnętrznych, a więc \( c_0=1 \). Każde drzewo o co najmniej jednym wierzchołku wewnętrznym rozkłada się jako \( T_l\wedge T_r \), dla pewnych jednoznacznie wyznaczonych poddrzew \( T_l,T_r \). Poddrzewo \( T_l \) nazywamy lewym, a \( T_r \) prawym podrzewem drzewa \( T_l\wedge T_r \).
Niech teraz
Zachodzi więc:
\( \vert{T}_{n_l,n_r}\vert=\vert {T}_{n_l}\times {T}_{n_r}\vert=\vert {T}_{n_l}\vert\cdot\vert {T}_{n_r}\vert=c_{n_l}\cdot c_{n_r}. \)
Ponadto, jeśli drzewo o \( n \) wierzchołkach wewnętrznych posiada lewe poddrzewo o \( n_l \) wierzchołkach wewnętrznych oraz prawe poddrzewo o \( n_r \) węzłów wewnętrznych to \( n=n_l+n_r+1 \). Zatem rodzina wszystkich drzew o \( n \) wewnętrznych wierzchołkach rozbija się na rozłączną sumę
\( {T}_n={T}_{0,n-1}\cup{T}_{1,n-2}\cup\ldots\cup{T}_{n-1,0}. \)
W konsekwencji otrzymujemy:
\( c_n=c_0 c_{n-1}+c_1 c_{n-2}+\ldots+ c_{n-1} c_0. \)
Wniosek 8.2
Funkcja tworząca \( {C}(x)=c_0+c_1x+c_2x^2+\ldots \) dla ciągu liczb Catalana spełnia
\( \displaystyle {C}(x)=\frac{1-\sqrt{1-4x}}{2x}. \)
Dowód
Używając zależności rekurencyjnej z Obserwacji 8.1 otrzymujemy:
\( \begin{align*} {C}(x) & =\sum_{n=0}^{\infty}c_nx^n \\ & =1+\sum_{n=1}^{\infty}(c_0 c_{n-1}+c_1 c_{n-2}+\ldots+ c_{n-1} c_0)x^n \\ & =1+x {C}(x) {C}(x), \end{align*} \)
skąd natychmiast:
\( {C}(x)=\frac{1\pm\sqrt{1-4x}}{2x}. \)
Warunek \( {C}(0)=c_0=1 \) eliminuje rozwiązanie \( {C}(x)\cdot 2x = 1+\sqrt{1-4x} \), a zatem
\( {C}(x)=\frac{1-\sqrt{1-4x}}{2x}. \)
Twierdzenie 8.3
Liczby Catalana wyrażają się wzorem
\( c_n=\frac{1}{n+1}{2n \choose n}. \)
Dowód
Twierdzenie o rozwinięciu funkcji \( (1+x)^y \) w szereg daje
\( \displaystyle \sqrt{1-4x}\ =\ \sum_{n=0}^{\infty}{1/2 \choose n}(-4x)^n. \)
Podstawiając powyższe rozwinięcie \( \sqrt{1-4x} \) do wzoru na \({C}(x) \) otrzymanego we Wniosku 8.2 po dokonaniu kilku prostych przekształceń otrzymujemy:
\( \displaystyle {C}(x) =\frac{1-\sqrt{1-4x}}{2x} =\sum_{n=0}^{\infty}\frac{(1-1/2)\cdot\ldots\cdot(n-1/2)}{(n+1)!}4^nx^n, \)
czyli
\( c_n = \frac{(1-1/2)\cdot\ldots\cdot(n-1/2)}{(n+1)!}4^n \)
Iloczyn \( (1-1/2)\cdot\ldots\cdot(n-1/2) \) po wymnożeniu przez \( 2^n \) przyjmuje postać
\( \displaystyle \prod_{k=1}^n(2k-1)=1\cdot3\cdot\ldots\cdot(2n-3)\cdot(2n-1). \)
Mnożąc więc teraz ten iloczyn \( 2^nn! \) otrzymujemy:
\( \displaystyle 2^n n!\prod_{k=1}^n(2k-1) =1\cdot2\cdot3\cdot\ldots\cdot(2n-2)\cdot(2n-1)\cdot2n=(2n)!. \)
Tym samym dostajemy
\( c_n=\frac{1}{n+1}{2n \choose n}. \)
Używając ostatniego Twierdzenia, można określic asymptotyczne zachowanie liczb Catalana.
Wniosek 8.4
Asymptotyczne zachowanie liczb Catalana dane jest przez
\( \displaystyle c_n\sim\frac{4^{n+1}}{4(n+1)\sqrt{\pi n}}, \)
tzn.
\( \displaystyle \lim_{n\mapsto \infty} \frac{c_n\cdot 4^{n+1}}{4(n+1)\sqrt{\pi n}}=1. \)
W praktyce często pojawia się konieczność zliczania drzew z uwagi na ich wysokość. Odpowiada to zliczaniu termów z uwagi na zagłębienie.
Wysokość drzewa określona jest rekurencyjnie jako:
Obserwacja 8.5
Liczba \( t_h \) drzew binarnych o wysokości co najwyżej \( h \) wyraża się równaniem rekurencyjnym
\( \left \{ \begin{array} {l} {rcl} t_0 & = & 1, \\ t_h & = & t_{h-1}^2+1\ \textrm{dla}\ h>1. \end{array} \right . \)
Dowód
Niech \( {T}_h \) będzie rodziną pełnych drzew binarnych o wysokości co najwyżej \( h \). Wtedy \( t_h=\vert {T}_h\vert \). Oczywiście \( {T}_0={\{ {\perp} \}\ } \), a więc \( t_0=1 \). Jedynym drzewem w \( {T}_h \), które nie jest rozkładalne na lewe i prawe poddrzewo jest drzewo \( \perp \). Każde więc drzewo \( T_0\in {T}_h-{\{ {\perp} \}\ } \) jest postaci \( T_0=T_l\wedge T_r \), gdzie poddrzewa \( T_l \) oraz \( T_r \) są wysokości co najwyżej \( h-1 \), tzn. \( T_l,T_r\in {T}_{h-1} \). Dowolne więc drzewo z \( {T}_h \) wyznacza jednoznacznie parę drzew z \( {T}_{h-1} \). Odwzorowanie to jest bijekcją, więc
\( \vert {T}_h\vert=\vert {T}_{h-1}\vert\cdot\vert {T}_{h-1}\vert+1, \)
skąd natychmiast dostajemy naszą zależność rekurencyjną.
Wniosek 8.6
Dla \( h\geq 1 \) mamy:
\( 2^{2^{h-1}}\leq t_h \leq 2^{2^{h}-1}, \)
Dowód
Dowód przeprowadzimy indukcyjnie ze względu na \( h \). Dla \( h=1 \) mamy \( t_1=t_0^2+1= 2 \), oraz \( 2^{2^{h-1}}= 2=2^{2^{h}-1} \) Niech więc \( h>1 \) i załóżmy dla indukcji, że
\( 2^{2^{h-2}}\leq t_{h-1}\leq 2^{2^{h-1}-1} \)
Wtedy:
\( \left(2^{2^{h-2}}\right)^2+1 \leq t_{h-1}^2+1 \leq \left(2^{2^{h-1}-1}\right)^2+1 \)
skąd natychmiast:
\( 2^{2^{h-1}}\leq \left(2^{2^{h-2}}\right)^2+1 \leq t_{h} \leq \left(2^{2^{h-1}-1}\right)^2+1 =2^{2^{h}-2}+1 =\frac{1}{4}2^{2^{h}}+1 \leq 2^{2^{h}-1} \)