Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

Obiekty kombinatoryczne często są zadane w sposób rekurencyjny. Tak zadawaliśmy np. drzewa binarne. Nawet, gdy obiekty nie są zadane w sposób rekurencyjny, to ich liczba (uzależniona np. od rozmiaru lub innego parametru) spełnia pewne zależności rekurencyjne. Często rozwikłanie takich zależności i wyprowadzenie wzoru na postać zwartą jest skomplikowane. W tym wykładzie zobaczymy jak w wielu przypadkach funkcje tworzące mogą być pomocne w zliczaniu różnych obiektów kombinatorycznych.

Zliczanie drzew

Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:

• $\perp$ jest drzewem binarnym,

• jeśli $T_0$ i $T_1$ są drzewami binarnymi to $T_0\wedge T_1$ też jest drzewem binarnym.

Węzeł wewnętrzny drzewa binarnego jest zdefiniowany rekurencyjnie:

• drzewo $\perp$ nie ma węzłów wewnętrznych,

• węzłami wewnętrznymi drzewa $T_0\wedge T_1$ są wszystkie węzły wewnętrzne drzew $T_0$ i $T_1$ a także nowy węzeł łączący drzewa $T_0$ i $T_1$.

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:

• zmienna $x$ jest wyrażeniem nawiasowym,

• jeśli $t_0$ i $t_1$ są wyrażeniami nawiasowymi, to $(t_0{t}_1)$ też jest wyrażeniem nawiasowym.

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ą:

$\{\begin{array}{rcl}{c}_0& =& 1,\\ c_n& =& c_0{c}_{n-1}+c_1{c}_{n-2}+\dots +c_{n-1}{c}_0,\text{<mrow data-mjx-texclass="ORD">dla</mrow>}n\ge 1.\end{array}$

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

• Parser nie mógł rozpoznać (nieznana funkcja „\rodzina”): {\displaystyle \rodzina{T}_n} będzie rodziną wszystkich drzew binarnych

o $n$ węzłach wewnętrznych, oraz

• Parser nie mógł rozpoznać (nieznana funkcja „\rodzina”): {\displaystyle \rodzina{T}_{n_l,n_r}} będzie rodziną wszystkich drzew,

których lewe i prawe poddrzewo mają odpowiednio $n_l$ oraz $n_r$ węzłów wewnętrznych.

Zachodzi więc:

Parser nie mógł rozpoznać (nieznana funkcja „\rodzina”): {\displaystyle \left\vert\rodzina{T}_{n_l,n_r}\right\vert=\left\vert\rodzina{T}_{n_l}\times\rodzina{T}_{n_r}\right\vert=\left\vert\rodzina{T}_{n_l}\right\vert\cdot\left\vert\rodzina{T}_{n_r}\right\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ę

Parser nie mógł rozpoznać (nieznana funkcja „\rodzina”): {\displaystyle \rodzina{T}_n=\rodzina{T}_{0,n-1}\cup\rodzina{T}_{1,n-2}\cup\ldots\cup \rodzina{T}_{n-1,0}. }

W konsekwencji otrzymujemy:

$c_n=c_0{c}_{n-1}+c_1{c}_{n-2}+\dots +c_{n-1}{c}_0.$

Wniosek 8.2

Funkcja tworząca Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)=c_0+c_1x+c_2x^2+\ldots} dla ciągu liczb Catalana spełnia

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)=\frac{1-\sqrt{1-4x}}{2x}. }

Dowód

Używając zależności rekurencyjnej z Obserwacji 8.1 otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{C}(x)&=&\sum_{n=0}^{\infty}c_nx^n\\ &=&1+\sum_{n=1}^{\infty}\left(c_0 c_{n-1}+c_1 c_{n-2}+\ldots+ c_{n-1} c_0\right)x^n\\ &=&1+x\fGen{C}(x)\fGen{C}(x), \endaligned}

skąd natychmiast:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)=\frac{1\pm\sqrt{1-4x}}{2x}. }

Warunek Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(0)=c_0=1} eliminuje rozwiązanie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)\cdot 2x = 1+\sqrt{1-4x}} , a zatem

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)=\frac{1-\sqrt{1-4x}}{2x}. }

Twierdzenie 8.3

Liczby Catalana wyrażają się wzorem

$c_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n}).$

Dowód

Twierdzenie o rozwinięciu funkcji $(1+x{)}^y$ w szereg daje

$\sqrt{1-4x}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{1/2}{n}){(-4x)}^n.$

Podstawiając powyższe rozwinięcie $\sqrt{1-4x}$ do wzoru na Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x)} otrzymanego we Wniosku 8.2 po dokonaniu kilku prostych przekształceń otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{C}(x) =\frac{1-\sqrt{1-4x}}{2x} =\sum_{n=0}^{\infty}\frac{\left(1-1/2\right)\cdot\ldots\cdot\left(n-1/2\right)}{\left(n+1\right)!}4^nx^n, }

czyli

$c_n=\frac{(1-1/2)\cdot \dots \cdot (n-1/2)}{(n+1)!}{4}^n$

Iloczyn $(1-1/2)\cdot \dots \cdot (n-1/2)$ po wymnożeniu przez $2^n$ przyjmuje postać

$\prod _{k=1}^n(2k-1)=1\cdot 3\cdot \dots \cdot (2n-3)\cdot (2n-1).$

Mnożąc więc teraz ten iloczyn $2^{n}n!$ otrzymujemy:

$2^{n}n!\prod _{k=1}^n(2k-1)=1\cdot 2\cdot 3\cdot \dots \cdot (2n-2)\cdot (2n-1)\cdot 2n=\left(2n\right)!.$

Tym samym dostajemy

$c_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n}).$

Używając ostatniego Twierdzenia, można określic asymptotyczne zachowanie liczb Catalana.