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). \)