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.
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} \)
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
\( {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
\( {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}-{\{ {0} \}\ } \) oraz \( a_0,a_1, \ldots, a_{k-1}\in{\{ {k_1, k_2, \ldots, k_m} \}\ } \).
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ą \( {P_{1,5,10,25,50}}(x) \).
Obserwacja 8.7
\( {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}=\lbrace\begin{array} {ll} 1, & \textrm{jeśli}\ n=ak\ \textrm{dla}\ a=0,1,2,\ldots \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} . \)
Otrzymujemy w ten sposób
\( \begin{align*} {P_k}(x) & =p_{k,0}+p_{k,1}x+p_{k,2}x^2+\ldots \\ & =1+x^k+x^{2k}+x^{3k}+\ldots, \end{align*} \)
która to funkcja zwija się do
\( {P_k}(x)\ =\ \frac{1}{1-x^k}. \)
Obserwacja 8.8
\( {P_{k_1,k_2,\ldots, k_m}}(x)\ =\ {P_{k_1}}(x)\cdot {P_{k_2}}(x)\cdot\ldots\cdot {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
\( (1+x^{k_1}+x^{2k_1}+\ldots)\cdot (1+x^{k_2}+x^{2k_2}+\ldots)\cdot\ \cdot(1+x^{k_m}+x^{2k_m}+\ldots) \)
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
\( \begin{align*} n & =j_1k_{l_1}+j_2k_{l_ 2}+\ldots+j_sk_{l_s} \\ & =(k_{l_1}+\ldots+k_{l_1})+(k_{l_2}+\ldots+k_{l_2})+\ldots+(k_{l_s}+\ldots+k_{l_s}), \end{align*} \)
tzn. \( p'_n \) jest liczbą rozkładów liczby \( n \) na sumy o składnikach ze zbioru \( {\{ {k_1, k_2,\ldots,k_n} \}\ } \), a zatem \( p'_n \) jest \( n \)-tym współczynnikiem funkcji tworzącej \( {P_{k_1,k_2,\ldots, k_m}}(x) \).
Przykład
Niech \( {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 \( {P_1}(x) \) oraz \( x^{2\cdot1} \) pochodzi z \( {P_2}(x) \), odpowiada sumie \( 6=1+1+1+1+2 \). Poniżej zaznaczono w funkcji tworzącej \( {P_{1,2,3,4}}(x) \) jednomiany \( \mathbf{x^{(1+1+1+1)}} \) oraz \( \mathbf{x^2} \)
\( \begin{array} {l} {P_{1,2,3,4}}(x)\ =\ 1+x+2x^2+3x^3+4x^4+6x^5+7x^6+\ldots \\ = \ (1 +x^1 +x^{(1+1)} +x^{(1+1+1)} +\mathbf{{x^{(1+1+1+1)}}} +x^{(1+1+1+1+1)} +x^{(1+1+1+1+1+1)} +\ldots) \\ = \cdot(1 +\mathbf{{x^2}} +x^{(2+2)} +x^{(2+2+2)} +x^{(2+2+2+2)} +x^{(2+2+2+2+2)} +\ldots) \\ = \cdot(1 +x^3 +x^{(3+3)} +x^{(3+3+3)} +x^{(3+3+3+3)} +x^{(3+3+3+3+3)} +\ldots) \\ = \cdot(1 +x^4 +x^{(4+4)} +x^{(4+4+4)} +x^{(4+4+4+4)} +x^{(4+4+4+4+4)} +\ldots) \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
\( {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
\( {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
\( {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 {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 \( {P_{(m)}}(x)= {P_{1,2,\ldots,m}}(x) \) rozwija się w szereg \( \displaystyle \sum_{n=0}^\infty p_{(m)n}x^n \), a formalny nieskończony splot
\( \displaystyle \prod_{k=1}^{\infty} {P_k}(x) = \prod_{k=1}^{\infty}\frac{1}{1-x^k} = \prod_{k=1}^{\infty}(1+x^k+x^{2k}+x^{3k}+\ldots) \)
zwija się do szeregu formalnego
\( {F}(x)=f_0+f_1x+f_2x^2+f_3x^3+\ldots \)
Oczywiście przy liczeniu \( f_n \) z czynników \( (1+x^k+x^{2k}+x^{3k}+\ldots) \), 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_{(n)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_{(n)n} \), skąd natychmiast \( f_n=p_n \), co kończy dowód.
Twierdzenie 8.10
Funkcja tworząca
\( {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 \( [\begin{array} {c}n \\ m\end{array} ] \) ma postać zwartą
\( {s_n}(x)=x^{\overline{n}}=x\cdot(x+1)\cdot(x+n-1). \)
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] & = & (n-1)\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 \( {s_k}(x) \) otrzymujemy
\( {s_n}(x)=(n-1) {s_{n-1}}(x)+x {s_{n-1}}(x)=(x+n-1) {s_{n-1}}(x). \)
Iterując powyższą równość otrzymujemy:
\( {s_n}{x}=(z+n-1)\cdot(z+n-2)\cdot\ldots\cdot(x+1)\cdot x= x^{\overline{n}}, \)
co kończy dowód.
Twierdzenie 8.11
Funkcja tworząca
\( \displaystyle {S_k}(x)=\left\{\begin{array}{c}k \\ k\end{array} \right\} +\left\{\begin{array}{c}k+1 \\ k\end{array}\right \}x+\left\{\begin{array}{c}k+2 \\ k\end{array}\right \}x^2+\left\{\begin{array}{c}k+3 \\ k\end{array}\right \}x^3+\ldots \)
dla podziałowych liczb Stirlinga \( \left\{\begin{array}{c}n \\ m\end{array} \right\} \) ma postać zwartą
\( {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\end{array} \right\} & = & 0, & \textrm{dla}\ n>0, \\ \left\{\begin{array}{c}k \\ k\end{array} \right\} & = & 1, & \textrm{dla}\ k\geq0, \\ \left\{\begin{array}{c}n+k \\ k\end{array} \right\} & = & k\left\{\begin{array}{c}n+k-1 \\ k\end{array} \right\}+\left\{\begin{array}{c}n+k-1 \\ k-1\end{array} \right\}, & \textrm{dla}\ n>1,\ k>0. \end{array} \)
Po podstawieniu tych zależności w rozwinięciu funkcji tworzącej \( {S_k}(x) \) otrzymujemy:
\( {S_k}(x)=kx {S_k}(x)+ {S_{k-1}}(x), \)
skąd natychmiast:
\( {S_k}(x)=\frac{1}{1-kx} {S_{k-1}}(x). \)
Iterując powyższą równość otrzymujemy:
\( {S_k}(x)=\frac{1}{(1-kx)\cdot(1-(k-1)x)\cdot\ldots\cdot(1-x)}, \)
co kończy dowód.
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 {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 {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ą
\( {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} & = 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 {B}(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n \) to
\( \displaystyle {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 \( {B}(x) \). Otrzymujemy więc równość
\( {B'}(x)=e^x {B}(x), \) (2)
której rozwiązaniem przyjmującym wartość \( {B}(0)=B_0=1 \) jest
\( {B}(x)=e^{(e^x-1)}. \)
Faktycznie, po podstawieniu rozwiązania do równości (2) uzyskujemy:
\( {B'}(x)=(e^{(e^x-1)})'=e^xe^{(e^x-1)}=e^x {B}(x). \)