Informatyka MIMUW

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