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

From Studia Informatyczne

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.

Spis treści

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.



Wszystkie pełne drzewa binarne o 3 węzłach wewnętrznych


Drzewo T posiadające lewe poddrzewo T_l oraz prawe poddrzewo Tr

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


\left\lbrace \begin{array} {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

  • \rodzina{T}_n będzie rodziną wszystkich drzew binarnych o n węzłach wewnętrznych, oraz
  • \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:


\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ę


\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}+\ldots+ c_{n-1} c_0.


image:End_of_proof.gif

Wniosek 8.2

Funkcja tworząca \fGen{C}(x)=c_0+c_1x+c_2x^2+\ldots dla ciągu liczb Catalana spełnia


\displaystyle \fGen{C}(x)=\frac{1-\sqrt{1-4x}}{2x}.


Dowód

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


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


\fGen{C}(x)=\frac{1\pm\sqrt{1-4x}}{2x}.


Warunek \fGen{C}(0)=c_0=1 eliminuje rozwiązanie \fGen{C}(x)\cdot 2x = 1+\sqrt{1-4x}, a zatem


\fGen{C}(x)=\frac{1-\sqrt{1-4x}}{2x}.


image:End_of_proof.gif

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}\left(-4x\right)^n.


Podstawiając powyższe rozwinięcie \sqrt{1-4x} do wzoru na \fGen{C}(x) otrzymanego we Wniosku 8.2 po dokonaniu kilku prostych przekształceń otrzymujemy:


\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{\left(1-1/2\right)\cdot\ldots\cdot\left(n-1/2\right)}{\left(n+1\right)!}4^n


Iloczyn \left(1-1/2\right)\cdot\ldots\cdot\left(n-1/2\right) po wymnożeniu przez 2^n przyjmuje postać


\displaystyle \prod_{k=1}^n\left(2k-1\right)=1\cdot3\cdot\ldots\cdot\left(2n-3\right)\cdot\left(2n-1\right).


Mnożąc więc teraz ten iloczyn 2^nn! otrzymujemy:


\displaystyle 2^n n!\prod_{k=1}^n\left(2k-1\right) =1\cdot2\cdot3\cdot\ldots\cdot\left(2n-2\right)\cdot\left(2n-1\right)\cdot2n=\left(2n\right)!.


Tym samym dostajemy


c_n=\frac{1}{n+1}{2n \choose n}.


image:End_of_proof.gif

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\left(n+1\right)\sqrt{\pi n}},


tzn.


\displaystyle \lim_{n\mapsto \infty} \frac{c_n\cdot 4^{n+1}}{4\left(n+1\right)\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:

  • \mbox{\sf h}(\perp)=0,
  • \mbox{\sf h}(T_0\wedge T_1)=\max\left(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) \right)+1.

Obserwacja 8.5

Liczba t_h drzew binarnych o wysokości co najwyżej h wyraża się równaniem rekurencyjnym


\left\lbrace \begin{array} {rcl} t_0&=&1,\\ t_h&=&t_{h-1}^2+1\ \textrm{dla}\ h>1. \end{array}  \right.


Dowód

Niech \rodzina{T}_h będzie rodziną pełnych drzew binarnych o wysokości co najwyżej h. Wtedy t_h=\left\vert\rodzina{T}_h\right\vert. Oczywiście \rodzina{T}_0={\left\{ {\perp} \right\}\ }, a więc t_0=1. Jedynym drzewem w \rodzina{T}_h, które nie jest rozkładalne na lewe i prawe poddrzewo jest drzewo \perp. Każde więc drzewo T_0\in\rodzina{T}_h-{\left\{ {\perp} \right\}\ } 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 \rodzina{T}_{h-1}. Dowolne więc drzewo z \rodzina{T}_h wyznacza jednoznacznie parę drzew z \rodzina{T}_{h-1}. Odwzorowanie to jest bijekcją, więc


\left\vert\rodzina{T}_h\right\vert=\left\vert\rodzina{T}_{h-1}\right\vert\cdot\left\vert\rodzina{T}_{h-1}\right\vert+1,


skąd natychmiast dostajemy naszą zależność rekurencyjną.

image:End_of_proof.gif


Drzewa o wysokości co najwyżej 2

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}

image:End_of_proof.gif

Zliczanie podziałów liczby na sumy

Przypomnijmy, że przez P(n,k) oznaczyliśmy liczbę podziałów liczby n na dokładnie k składników. Wtedy \displaystyle p_n = \sum_{k=1}^n P(n,k) oznacza liczbę wszystkich możliwych podziałów liczby n na sumę.

Przykład

Policzmy wszystkie sposoby przedstawienia liczby 6 za pomocą sumy dodatnich liczb naturalnych.


6=a_0+a_1+\ldots+a_{k-1},


gdzie k oraz \displaystyle a_0\leq a_1 \leq \ldots \leq a_{k-1} są dodatnimi liczbami naturalnymi. Oto one


\begin{array} {rclp{2cm}rcl} 6&=&1+1+1+1+1+1& & 6&=&2+2+2\\ 6&=&1+1+1+1+2& & 6&=&1+5\\ 6&=&1+1+1+3& & 6&=&2+4\\ 6&=&1+1+2+2& & 6&=&3+3\\ 6&=&1+1+4& & 6&=&6\\ 6&=&1+2+3&&&& \end{array}


tzn. p_6 =11.

Funkcja tworząca podziału liczby na sumy to szereg


\fGen{P}(x)=p_0+p_1x+p_2x^2+p_3x^3+\ldots


Ponadto funkcja tworząca podziału liczby na sumy złożone wyłącznie z liczb k_1, k_2, \ldots, k_m oznaczać będziemy przez


\fGen{P_{k_1,k_2,\ldots, k_m}}(x)=p'_0+p'_1x+p'_2x^2+p'_3x^3+\ldots,


gdzie p'_n to liczba podziałów liczby n na sumę n=a_0+a_1+\ldots+a_{k-1}, gdzie k\in\mathbb{N}-{\left\{ {0} \right\}\ } oraz a_0,a_1, \ldots, a_{k-1}\in{\left\{ {k_1, k_2, \ldots, k_m} \right\}\ }.

Przykład

Pierwszy przykład w wykładzie o funkcjach tworzących dotyczył możliwości rozmiany kwoty za pomocą jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Rozważaliśmy więc tam funkcję tworzącą \fGen{P_{1,5,10,25,50}}(x).

Obserwacja 8.7


\fGen{P_k}(x)=1+x^k+x^{2k}+x^{3k}+\ldots=\frac{1}{1-x^k}.


Dowód

Niech p_{k,n} będzie liczbą rozkładów liczby n na sumę złożoną wyłącznie ze składników równych k. Oczywiście jeśli k dzieli n, to istnieje dokładnie jedna suma n=k+k+\dots+k. Jeśli natomiast n nie jest podzielne przez k, to taki rozkład nie istnieje, tak więc


p_{k,n}=\left\lbrace\begin{array} {ll} 1,&\textrm{jeśli}\ n=ak\ \textrm{dla}\ a=0,1,2,\ldots\\ 0,&\textrm{w przeciwnym wypadku.} \end{array} \right.


Otrzymujemy w ten sposób


\aligned \fGen{P_k}(x)&=p_{k,0}+p_{k,1}x+p_{k,2}x^2+\ldots\\ &=1+x^k+x^{2k}+x^{3k}+\ldots,  \endaligned


która to funkcja zwija się do


\fGen{P_k}(x)\ =\ \frac{1}{1-x^k}.


image:End_of_proof.gif

Obserwacja 8.8


\fGen{P_{k_1,k_2,\ldots, k_m}}(x)\  =\  \fGen{P_{k_1}}(x)\cdot\fGen{P_{k_2}}(x)\cdot\ldots\cdot\fGen{P_{k_m}}(x) =\  \frac{1}{1-x^{k_1}}\cdot\frac{1}{1-x^{k_2}}\cdot\ldots\cdot\frac{1}{1-x^{k_m}}.


Dowód

Załóżmy, że splot


\left(1+x^{k_1}+x^{2k_1}+\ldots\right)\cdot \left(1+x^{k_2}+x^{2k_2}+\ldots\right)\cdot\  \cdot\left(1+x^{k_m}+x^{2k_m}+\ldots\right)


jest przedstawiony jako szereg p'_0+p'_1x+p'_2x^2+p'_3x^3+\ldots. Wtedy oczywiście p'_nx^n jest sumą wszystkich jednomianów postaci x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}}, dla których x^n=x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}}. Współczynnik p'_n więc jest liczbą wszystkich ciągów s,j_1,\ldots,j_s,l_1,\ldots,l_s takich, że


\aligned n&=j_1k_{l_1}+j_2k_{l_ 2}+\ldots+j_sk_{l_s}\\ &=\left(k_{l_1}+\ldots+k_{l_1}\right)+\left(k_{l_2}+\ldots+k_{l_2}\right)+\ldots+\left(k_{l_s}+\ldots+k_{l_s}\right), \endaligned


tzn. p'_n jest liczbą rozkładów liczby n na sumy o składnikach ze zbioru {\left\{ {k_1, k_2,\ldots,k_n} \right\}\ }, a zatem p'_n jest n-tym współczynnikiem funkcji tworzącej \fGen{P_{k_1,k_2,\ldots, k_m}}(x).

image:End_of_proof.gif

Przykład

Niech \fGen{P_{1,2,3,4}}(x)=p''_0+p''_1x+p''_2x^2+\ldots. Współczynnik p''_6 to liczba iloczynów postaci x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}} równych x^6, a zarazem liczba podziałów liczby 6 na sumy złożone ze składników 1,2,3 oraz 4. Każdemu iloczynowi odpowiada jeden podział. Na przykład x^{1\cdot4}\cdot x^{2\cdot1}, gdzie x^{1\cdot4} pochodzi z \fGen{P_1}(x) oraz x^{2\cdot1} pochodzi z \fGen{P_2}(x), odpowiada sumie 6=1+1+1+1+2. Poniżej zaznaczono w funkcji tworzącej \fGen{P_{1,2,3,4}}(x) jednomiany \mathbf{x^{\left(1+1+1+1\right)}} oraz \mathbf{x^2}


\begin{array} {l}  \fGen{P_{1,2,3,4}}(x)\ =\ 1+x+2x^2+3x^3+4x^4+6x^5+7x^6+\ldots\\ = \ \left(1  +x^1  +x^{\left(1+1\right)}  +x^{\left(1+1+1\right)}  +\mathbf{{x^{\left(1+1+1+1\right)}}}  +x^{\left(1+1+1+1+1\right)}  +x^{\left(1+1+1+1+1+1\right)}  +\ldots\right)\\ =   \cdot\left(1  +\mathbf{{x^2}}  +x^{\left(2+2\right)}  +x^{\left(2+2+2\right)}  +x^{\left(2+2+2+2\right)}  +x^{\left(2+2+2+2+2\right)}   +\ldots\right)\\ =   \cdot\left(1  +x^3  +x^{\left(3+3\right)}  +x^{\left(3+3+3\right)}  +x^{\left(3+3+3+3\right)}  +x^{\left(3+3+3+3+3\right)}   +\ldots\right)\\ =   \cdot\left(1  +x^4  +x^{\left(4+4\right)}  +x^{\left(4+4+4\right)}  +x^{\left(4+4+4+4\right)}  +x^{\left(4+4+4+4+4\right)}   +\ldots\right) \end{array}


Odpowiadają one zaznaczonemu rozkładowi na liście wszystkich rozkładów liczby 6:


\begin{array} {lp{2cm}l} 6\ =\ 1+1+1+1+1+1,& & 6\ =\ 1+2+3,\\ \mathbf{\underline{6\ =\ 1+1+1+1+2}},& & 6\ =\ 2+2+2,\\ 6\ =\ 1+1+1+3,& & 6\ =\ 3+3.\\ 6\ =\ 1+1+2+2,& &  \end{array}


Przykład

W funkcji tworzącej


\fGen{P_{1,5,10,25,50}}(x)=p'''_0+p'''_1x+p'''_2x^2+\ldots.


współczynnik p'''_n jest liczbą podziałów liczby n na sumy postaci


n=1+\ldots+1+5+\ldots+5+10+\ldots+10+25+\ldots+25+50+\ldots+50,


czyli liczbą sposobów na jakie można rozmienić n centów przy użyciu jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Otrzymaliśmy więc rozwiązanie przykładu o rozmienianiu monet. Funkcja tworząca jest w poznanej już postaci równej


\fGen{P_{1,5,10,25,50}}(x)=\frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{25}}\cdot\frac{1}{1-x^{50}}.


Widzieliśmy już, że ogólnie


\fGen{P_{k_1k_2\ldots k_m}}(x)\  =\  \frac{1}{1-x^{k_1}}\cdot\frac{1}{1-x^{k_2}}\cdot\ldots\cdot\frac{1}{1-x^{k_m}}.


Twierdzenie 8.9[L. Euler]

Funkcja tworząca podziału liczby na sumy jest przedstawialna jako


\displaystyle \fGen{P}(x)=\prod_{k=1}^{\infty}\frac{1}{1-x^k} =\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\ldots\cdot\frac{1}{1-x^n}\cdot\ldots


Dowód

Niech \fGen{P_{\left(m\right)}}(x)=\fGen{P_{1,2,\ldots,m}}(x) rozwija się w szereg \displaystyle \sum_{n=0}^\infty p_{\left(m\right)n}x^n, a formalny nieskończony splot


\displaystyle \prod_{k=1}^{\infty}\fGen{P_k}(x)  = \prod_{k=1}^{\infty}\frac{1}{1-x^k} = \prod_{k=1}^{\infty}\left(1+x^k+x^{2k}+x^{3k}+\ldots\right)


zwija się do szeregu formalnego


\fGen{F}(x)=f_0+f_1x+f_2x^2+f_3x^3+\ldots


Oczywiście przy liczeniu f_n z czynników \left(1+x^k+x^{2k}+x^{3k}+\ldots\right), gdzie k>n, jedynie jednomian 1 odgrywa rolę, gdyż jednomiany x^{lk} z l\geq1 dają zbyt duże potęgi. A zatem f_n=p_{\left(n\right)n}. Ponieważ żaden składnik w rozkładzie n=a_0+a_1+\ldots+a_s nie może przekraczać n, mamy p_n=p_{\left(n\right)n}, skąd natychmiast f_n=p_n, co kończy dowód.

image:End_of_proof.gif

Funkcje tworzące dla liczb Stirlinga oraz liczb Bella

Twierdzenie 8.10

Funkcja tworząca


\fGen{s_n}(x)=\left[\begin{array} {c}n\\ 0\end{array} \right]+\left[\begin{array} {c}n\\ 1\end{array} \right]x+\left[\begin{array} {c}n\\ 2\end{array} \right]x^2+\left[\begin{array} {c}n\\ 3\end{array} \right]x^3+\ldots,


dla cyklowych liczb Stirlinga \left[\begin{array} {c}n\\ m\end{array} \right] ma postać zwartą


\fGen{s_n}(x)=x^{\overline{n}}=x\cdot\left(x+1\right)\cdot\left(x+n-1\right).


Dowód

Cyklowe liczby Stirlinga spełniają następującą zależność rekurencyjną


\begin{array} {rcll} \left[\begin{array} {c}n\\ 0\end{array} \right]&=&0,&\textrm{dla}\ n>0,\\ \left[\begin{array} {c}n\\ k\end{array} \right]&=&0,&\textrm{dla}\ k<n,\\ \left[\begin{array} {c}k\\ k\end{array} \right]&=&1,&\textrm{dla}\ k\geq0,\\ \left[\begin{array} {c}n\\ k\end{array} \right]&=&\left(n-1\right)\left[\begin{array} {c}n-1\\ k\end{array} \right]+\left[\begin{array} {c}n-1\\ k-1\end{array} \right],&\textrm{dla}\ 0>k>n. \end{array}


Po podstawieniu tych zależności w rozwinięciu funkcji tworzącej \fGen{s_k}(x) otrzymujemy


\fGen{s_n}(x)=\left(n-1\right)\fGen{s_{n-1}}(x)+x\fGen{s_{n-1}}(x)=\left(x+n-1\right)\fGen{s_{n-1}}(x).


Iterując powyższą równość otrzymujemy:


\fGen{s_n}{x}=\left(z+n-1\right)\cdot\left(z+n-2\right)\cdot\ldots\cdot\left(x+1\right)\cdot x= x^{\overline{n}},


co kończy dowód.

image:End_of_proof.gif

Twierdzenie 8.11

Funkcja tworząca


\displaystyle \fGen{S_k}(x)=\left\{\begin{array}{c}k\\ k\endarray \right\} +\left\{\begin{array}{c}k+1\\ k\endarray \right\}x+\left\{\begin{array}{c}k+2\\ k\endarray \right\}x^2+\left\{\begin{array}{c}k+3\\ k\endarray \right\}x^3+\ldots


dla podziałowych liczb Stirlinga \left\{\begin{array}{c}n\\ m\endarray \right\} ma postać zwartą


\fGen{S_k}(x)=\frac{1}{(1-x)\cdot(1-2x)\cdot\ldots\cdot(1-kx)}.


Dowód

Podziałowe liczby Stirlinga spełniają następującą zależność rekurencyjną


\begin{array} {rcll} \left\{\begin{array}{c}n\\ 0\endarray \right\}&=&0,&\textrm{dla}\ n>0,\\ \left\{\begin{array}{c}k\\ k\endarray \right\}&=&1,&\textrm{dla}\ k\geq0,\\ \left\{\begin{array}{c}n+k\\ k\endarray \right\}&=&k\left\{\begin{array}{c}n+k-1\\ k\endarray \right\}+\left\{\begin{array}{c}n+k-1\\ k-1\endarray \right\},&\textrm{dla}\ n>1,\ k>0. \end{array}


Po podstawieniu tych zależności w rozwinięciu funkcji tworzącej \fGen{S_k}(x) otrzymujemy:


\fGen{S_k}(x)=kx\fGen{S_k}(x)+\fGen{S_{k-1}}(x),


skąd natychmiast:


\fGen{S_k}(x)=\frac{1}{1-kx}\fGen{S_{k-1}}(x).


Iterując powyższą równość otrzymujemy:


\fGen{S_k}(x)=\frac{1}{(1-kx)\cdot(1-(k-1)x)\cdot\ldots\cdot(1-x)},


co kończy dowód.

image:End_of_proof.gif

Czasem, dla liczenia współczynników funkcji tworzącej wygodnie użyć jest rachunku różniczkowego i rozwinięcia funkcji w szereg Taylora. Dlatego dla ciągu (g_0,g_1,g_2,g_3,\ldots) obok funkcji tworzącej


\displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.


rozważa się też tzw. wykładniczą funkcję tworzącą, tzn. wyrażenie postaci


\displaystyle \sum_{n=0}^{\infty}{\frac{g_n}{n!}x^n} =\frac{g_0}{0!}+\frac{g_1}{1!}x+\frac{g_2}{2!}x^2+\frac{g_3}{3!}x^3+\frac{g_4}{4!}x^4+\ldots.


Twierdzenie 8.12

Wykładnicza funkcja tworząca


\displaystyle \fGen{B}(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=\frac{B_0}{0!}+\frac{B_1}{1!}x+\frac{B_2}{2!}x^2+\frac{B_3}{3!}x^3+\ldots


dla liczb Bell'a B_0,B_1,B_2,B_3,\ldots ma postać zwartą


\fGen{B}(x)=e^{(e^x-1)}.


Dowód

Liczby Bella spełniają następującą zależność rekurencyjną


\begin{array} {rcl} B_0&=&1,\\ B_{n+1} &=&{n \choose 0}B_0+{n \choose 1}B_1+{n \choose 2}B_2+\ldots+{n \choose n}B_n,\quad\textrm{dla}\ n>0. \end{array}


Pochodna szeregu \displaystyle \fGen{B}(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n to


\displaystyle \fGen{B'}(x) =\sum_{n=1}^{\infty}\frac{n B_n}{n!}x^{n-1}  = \sum_{n=0}^{\infty}\frac{B_n}{n!}x^{n}.


Dzieląc obustronnie przez n! zależność rekurencyjną dla liczb Bella otrzymujemy


\frac{1}{n!}\cdot B_{n+1} = \frac{1}{0!}\cdot \frac{1}{n!}\cdot B_0+\frac{1}{1!}\cdot \frac{1}{(n-1)!}\cdot B_1+\ldots+\frac{1}{n!}\cdot\frac{1}{0!} \cdot B_n


Prawa strona tej równości jest współczynnikiem przy x^n splotu funkcji e^x z \fGen{B}(x). Otrzymujemy więc równość image:End_of_proof.gif


\fGen{B'}(x)=e^x\fGen{B}(x),      (2)


której rozwiązaniem przyjmującym wartość \fGen{B}(0)=B_0=1 jest


\fGen{B}(x)=e^{(e^x-1)}.


Faktycznie, po podstawieniu rozwiązania do równości (2) uzyskujemy:


\fGen{B'}(x)=(e^{(e^x-1)})'=e^xe^{(e^x-1)}=e^x\fGen{B}(x).