01ZTGA:Kapitola3 2
Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 15:22, kterou vytvořil Karel.brinda (diskuse | příspěvky)
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ZTGA
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01ZTGA | Karel.brinda | 16. 1. 2012 | 00:45 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:51 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 13:34 | header.tex | |
Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 13:36 | cast0.tex | |
Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 13:46 | cast1_kapitola1.tex | |
Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 13:49 | cast1_kapitola2.tex | |
Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 13:50 | cast1_kapitola3.tex | |
Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 10:06 | cast1_kapitola4.tex | |
Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 13:51 | cast1_kapitola5.tex | |
Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 13:53 | cast1_kapitola6.tex | |
Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 14:34 | cast1_kapitola7.tex | |
Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 14:40 | cast1_kapitola8.tex | |
Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 14:44 | cast1_kapitola9.tex | |
Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:48 | cast1_kapitola10.tex | |
Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:52 | cast1_kapitola11.tex | |
Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 14:56 | cast1_kapitola12.tex | |
Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 14:57 | cast1_kapitola13.tex | |
Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 15:11 | cast2_kapitola1.tex | |
Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 15:12 | cast2_kapitola2.tex | |
Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 15:16 | cast2_kapitola3.tex | |
Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 15:18 | cast2_kapitola4.tex | |
Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 15:22 | cast3_kapitola1.tex | |
Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 15:22 | cast3_kapitola2.tex |
Zdrojový kód
%\wikiskriptum{01ZTGA} \section{Exponenciální generující funkce} \begin{defn} \label{def:EGF}Nechť $z\in\C$, $\left(a_{n}\right)_{n=0}^{\infty}$ je číselná posloupnost. \textbf{Řadou s exponenciální generující funkcí} (angl. \emph{exponential generating function}, EGF) rozumíme číselnou řadu\[ \sum_{k=0}^{n}\frac{a_{n}}{n!}z^{n}.\] Součet této řady nazýváme (exponenciální) \textbf{generující funkcí}. Korespondenci posloupnosti koeficientů řady a příslušné exponenciální generujcí funkce $f(z)$ zapisujeme jako\[ \left(a_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}f(z).\] \end{defn} \begin{rem*} Srovnáme-li definice \ref{def:OPS} a \ref{def:EGF}, všimneme si určité inkonzistence v názvosloví. Definice \ref{def:OPS} udává název pro řadu, ale definice \ref{def:EGF} hovoří spíše o její generující funkci. Tento rozpor je dědictvím přednášky, kde jsme ve skutečnosti žádné formální definice neměli a hovořili jsme o obyčejných generujících funkcích (angl. \emph{ordinary power} \textbf{\emph{series}}, OPS) a o exponenciálních generujících funkcích, které jsme označovali jako EGF. Zájemci o korektní (a/nebo obvyklé) označení jej budou muset hledat v literatuře. \end{rem*} \begin{example*} \[ \left(1\right)_{n=1}^{\infty}\xrightarrow{EGF}\e^{z}=\sum_{n=0}^{\infty}\frac{z^{n}}{n!}.\] \end{example*} \subsection{Pravidla pro počítání s EGF\label{sub:Pravidla-pro-pocitani-s-EGF}} Jestliže \[ \left(a_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}f(z),\;\left(b_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}g(z),\] tak potom lze odvodit následující vztahy: \begin{enumerate} \item Pro posunutí indexu o 1 platí\[ \boxed{\left(a_{n+1}\right)_{n=0}^{\infty}\xrightarrow{EGF}f'(z)},\] protože\[ f'(z)=\sum_{n=1}^{\infty}\frac{a_{n}}{n!}nz^{n-1}=\sum_{n=1}^{\infty}\frac{a_{n}}{(n-1)!}z^{n-1}=\sum_{n=0}^{\infty}\frac{a_{n+1}}{n!}z^{n}.\] \item Pro násobení indexem platí\[ \boxed{\left(na_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}zf'(z)},\] protože\[ f'(z)=\sum_{n=1}^{\infty}\frac{a_{n}}{n!}nz^{n-1}=\frac{1}{z}\sum_{n=0}^{\infty}\frac{\left(n\cdot a_{n}\right)}{n!}z^{n}.\] \item Pro násobení mocninou konstanty platí zřejmě (stejně jako u OPS)\[ \boxed{\left(c^{n}a_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}f(cz)}.\] \item Zřejmě platí\begin{equation} \boxed{\left(a_{n}\pm b_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}f(z)\pm g(z)}.\label{eq:Soucet-rozdil-EGF}\end{equation} \item Podle vzorce pro násobení mocninných řad platí\[ \boxed{\left(\sum_{k=0}^{n}\binom{n}{k}a_{k}b_{n-k}\right)_{n=0}^{\infty}\xrightarrow{EGF}f(z)g(z)},\] protože\[ \left(\sum_{n=0}^{\infty}\frac{a_{n}}{n!}z^{n}\right)\left(\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{a_{k}}{k!}\frac{b_{n-k}}{(n-k)!}\right)z^{n}=\sum_{n=0}^{\infty}\frac{1}{n!}\left(\sum_{k=0}^{n}\underbrace{\frac{n!}{k!(n-k)!}}_{\binom{n}{k}}a_{k}b_{n-k}\right)z^{n}.\] \item Speciálně pro volbu $b_{n}=1$ je $g(z)=\e^{z}$, a tak\begin{equation} \boxed{\left(\sum_{k=0}^{n}\binom{n}{k}a_{k}\right)_{n=0}^{\infty}\xrightarrow{EGF}\e^{z}f(z)}.\label{eq:castec-souc-EGF}\end{equation} \end{enumerate} \subsection{Jednoduchý příklad} \begin{rem*} Je zřejmé, že použití generujících funkcí je podmíněno nenulovým poloměrem konvergence příslušných řad. Jak již bylo řečeno, v kombinatorických úlohách zpravidla hledáme posloupnost koeficientů $\left(a_{n}\right)_{n=0}^{\infty}$. Tuto posloupnost sice neznáme, ale v mnoha případech jsme schopni ji nějakým způsobem odhadnout, takže můžeme zdola odhadnout i poloměr konvergence. Kritériem rozhodování, zda pro řešení dané úlohy použít OPS či EGF, může být právě fakt, že EGF připouští pomalejší klesání posloupnosti $a_{n}$ (o faktor $n!$) při zachování stejného poloměru konvergence. Při rozhodování nám mnohdy pomůže též ,,typ{}`` úlohy - například následující úloha vybízí k použití EGF, neboť její zadání v mnohém připomíná pravidlo (\ref{eq:castec-souc-EGF}). \end{rem*} \begin{example} Vypočítejte součet\[ S_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{2}.\] Vyjděme z posloupnosti $\left(1\right)_{n=0}^{\infty}$ a používejme postupně pravidla z části \ref{sub:Pravidla-pro-pocitani-s-EGF}:\begin{eqnarray*} \left(1\right)_{n=0}^{\infty} & \xrightarrow{EGF} & \e^{z},\\ \left(n\cdot1\right)_{n=0}^{\infty} & \xrightarrow{EGF} & z\e^{z},\\ \left(n^{2}\right)_{n=0}^{\infty}=\left(n\cdot n\right)_{n=0}^{\infty} & \xrightarrow{EGF} & z\left(\e^{z}+z\e^{z}\right)=\left(z+z^{2}\right)\e^{z},\\ \left(S_{n}\right)_{n=0}^{\infty}=\left(\sum_{k=0}^{n}\binom{n}{k}k^{2}\right)_{n=0}^{\infty} & \xrightarrow{EGF} & \left(z+z^{2}\right)\e^{2z}.\end{eqnarray*} Podle posledního řádku platí\[ \sum_{n=0}^{\infty}\frac{S_{n}}{n!}z^{n}=\left(z+z^{2}\right)\e^{2z}.\] Najdeme-li tedy rozvoj funkce $\left(z+z^{2}\right)\e^{2z}$ do mocninné řady, budeme schopni vyjádřit koeficienty $S_{n}$. Rozvoj sestrojíme šikovně, neboť nám postačí znalost rozvoje $\e^{z}$, který vynásobíme polynomem $\left(z+z^{2}\right)$, takže výsledek bude stále mocninná řada.\[ \left(z+z^{2}\right)\e^{2z}=\left(z+z^{2}\right)\sum_{n=0}^{\infty}\frac{1}{n!}\left(2z\right)^{n}=\sum_{n=0}^{\infty}\frac{2^{n}}{n!}z^{n+1}+\sum_{n=0}^{\infty}\frac{2^{n}}{n!}z^{n+2}=\underbrace{z+\sum_{n=2}^{\infty}\frac{2^{n-1}}{\left(n-1\right)!}z^{n}}_{\sum_{n=1}^{\infty}\frac{2^{n-1}}{\left(n-1\right)!}z^{n}}+\sum_{n=2}^{\infty}\frac{2^{n-2}}{\left(n-2\right)!}z^{n}.\] Z uvedeného vztahu je už vidět, že $S_{1}=1$ a\begin{eqnarray*} \frac{S_{n}}{n!} & = & \frac{2^{n-1}}{\left(n-1\right)!}+\frac{2^{n-2}}{\left(n-2\right)!},\\ S_{n} & = & n2^{n-1}+n(n-1)2^{n-2}.\end{eqnarray*} \end{example} \subsection{Bernoulliova čísla} \begin{defn} Bernoulliovými čísly rozumíme posloupnost $\left(B_{n}\right)_{n=0}^{\infty}$, pro niž platí \[ \left(B_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}\frac{z}{\e^{z}-1}.\] \end{defn} \begin{rem} \label{rem:korektnost-definice-Bn}Zabývejme se korektností definice $B_{n}$, tj. je-li možné psát funkci $f(z)=\frac{z}{\e^{z}-1}$ jako součet mocninné řady. Nejprve se podívejme na kořeny jmenovatele. Jestliže vyjádříme $z$ jako $z=i\varphi$, můžeme řešit rovnici\begin{eqnarray*} \e^{i\varphi} & = & 1,\textrm{ tj.}\\ \cos\varphi+i\sin\varphi & = & 1,\end{eqnarray*} která má řešení $\varphi=2k\pi$, neboli $z=2k\pi i$, kde $k\in\Z$. V bodě $z_{0}=0$ ($k=0$) platí\[ \lim_{z\to z_{0}}\frac{z}{\e^{z}-1}=1,\] a v tomto bodě je tedy odstranitelná nespojitost funkce $f$. Pro $k\in\Z\backslash\left\{ 0\right\} $ a $z_{0}=2k\pi i$ však platí\[ \lim_{z\to z_{0}}\frac{z}{\e^{z}-1}=\infty,\] přičemž nejblíže nule jsou body $\pm2\pi i$. Jiné singulární body funkce $f$ nemá. To znamená, že je holomorfní na kruhu se středem v bodě $0$ a s poloměrem $2\pi$ a její Laurentův rozvoj v bodě $0$ má tedy jen regulární část - je to přímo Taylorův rozvoj. Proto lze skutečně funkci $\frac{z}{\e^{z}-1}$ rozvinout do mocninné řady (v bodě $0$) a poloměr konvergence této řady je $2\pi$ (neboť to je vzdálenost k nejbližšímu singulárnímu bodu). \end{rem} V následujícím se budeme snažit najít hodnoty $B_{n}$. Podle definice po vynásobení $(\e^{z}-1)$ platí% \footnote{Od tohoto okamžiku jsme se zbavili odstranitelné nespojitosti funkce $f(z)=\frac{z}{\e^{z}-1}$ v bodě $0$. Pokud v bodě $0$ dodefinujeme funkci $f$ její limitou, tj. číslem $1$, tak je koeficient $B_{0}$ v rozvoji funkce $f$ do mocninné řady roven jedné, neboť to je právě funkční hodnota v bodě $0$. Jak uvidíme, po odstranění zlomku k tomuto výsledku dojdeme i jinak.% }\[ z=\sum_{n=0}^{\infty}\frac{B_{n}}{n!}z^{n}\cdot\underbrace{\sum_{n=1}^{\infty}\frac{1}{n!}z^{n}}_{\e^{z}-1}.\] Po úpravě dostaneme\[ 1=\sum_{n=0}^{\infty}\frac{B_{n}}{n!}z^{n}\sum_{n=0}^{\infty}\frac{1}{\left(n+1\right)!}z^{n}.\] Podle vzorce pro součin mocninných řad můžeme dále upravit na\[ 1=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{B_{k}}{k!}\frac{1}{\left(n-k+1\right)!}\right)z^{n}=\sum_{n=0}^{\infty}c_{n}z^{n},\] ale to není nic jiného než rozvoj ,,funkce{}`` $g(z)=1$ do mocninné řady. Protože koeficienty rozvoje jsou jednoznačné, platí\begin{eqnarray*} c_{0}=B_{0} & = & 1,\\ c_{n}=\sum_{k=0}^{n}\frac{B_{k}}{k!}\frac{1}{\left(n-k+1\right)!} & = & 0,\; n\in\N.\end{eqnarray*} Po vynásobení poslední rovnosti číslem $n!$ přejde tato rovnost na elegantnější tvar\[ \sum_{k=0}^{n}\binom{n+1}{k}B_{k}=0.\] S pomocí tohoto vztahu jsme schopni rekurzivně vypočítat prvky posloupnosti $\left(B_{n}\right)$: \begin{itemize} \item $B_{1}=-\frac{1}{2}$ zjistíme ze vztahu $\binom{2}{0}B_{0}+\binom{2}{1}B_{1}=0$, \item $B_{2}=\frac{1}{6}$ vypočítáme z rovnosti $\binom{3}{0}B_{0}+\binom{3}{1}B_{1}+\binom{3}{2}B_{2}=0$, \end{itemize} a takto můžeme pokračovat. Prvních 16 členů posloupnosti $\left(B_{n}\right)$ má následující hodnoty: \begin{center}\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $n$& $0$& $1$& $2$& $3$& $4$& $5$& $6$& $7$\tabularnewline \hline $B_{n}$& $1$& $-\frac{1}{2}$& $\frac{1}{6}$& $0$& $-\frac{1}{30}$& $0$& $\frac{1}{42}$& $0$\tabularnewline \hline \end{tabular}\\ \begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline $8$& $9$& $10$& $11$& $12$& $13$& $14$& $15$& $16$\tabularnewline \hline $-\frac{1}{30}$& $0$& $\frac{5}{66}$& $0$& $-\frac{691}{2730}$& $0$& $\frac{7}{6}$& $0$& $-\frac{3617}{510}$\tabularnewline \hline \end{tabular}\end{center} Hodnoty $B_{n}$ se mění na první pohled chaoticky a explicitní vyjádření členů posloupnosti $B_{n}$ nevypadá jednoduše. My se o něj ani pokoušet nebudeme. Podle hodnot v tabulce však můžeme předpokládat, že\[ B_{2n+1}=0\textrm{ pro }n\geq1.\] To je z definice $B_{n}$ ekvivalentní vztahu\[ \frac{z}{\e^{z}-1}=1-\frac{1}{2}z+\textrm{sudé mocniny }z.\] Abychom jej dokázali, stačí ukázat, že funkce $f(z)=\frac{z}{\e^{z}-1}+\frac{1}{2}z$ je sudá. To skutečně platí, můžeme ověřit rovnost $f(z)=f(-z)$ nebo provést úpravu $f(z)$ na tvar\[ \frac{z}{\e^{z}-1}+\frac{z}{2}=z\frac{2+\e^{z}-1}{2(e^{z}-1)}=\frac{z}{2}\frac{\e^{z}+1}{\e^{z}-1}=\frac{z}{2}\frac{\e^{\frac{z}{2}}+\e^{-\frac{z}{2}}}{\e^{\frac{z}{2}}-\e^{-\frac{z}{2}}}=\frac{z}{2}\coth\left(\frac{z}{2}\right),\] z nejž je již sudost funkce $f$ zřejmá. \begin{thm} \textbf{\emph{(Bernoulli)}} Nechť $m\in\N$. Potom platí\[ \sum_{k=0}^{n-1}k^{m}=\frac{1}{m+1}\sum_{i=0}^{m}\binom{m+1}{i}B_{i}n^{m-i+1}.\] \end{thm} \begin{example*} Pro $m=2$ máme známý vzoreček\begin{eqnarray*} \sum_{k=0}^{n}k^{2} & = & \frac{1}{6}n(n+1)(2n+1),\;\textrm{tj.}\\ \sum_{k=0}^{n-1}k^{2} & = & \frac{1}{6}(n-1)n(2n-1)\end{eqnarray*} a podle Bernoulliovy věty vychází\[ \sum_{k=0}^{n-1}k^{2}=\frac{1}{3}\left(B_{0}n^{3}+3\underbrace{B_{1}}_{-\frac{1}{2}}n^{2}+3\underbrace{B_{2}}_{\frac{1}{6}}n\right)=\frac{1}{3}n\left(n^{2}-\frac{3}{2}n+\frac{1}{2}\right)=\frac{1}{6}n\left(2n^{2}-3n+1\right)=\frac{1}{6}n(n-1)(2n-1).\] \end{example*} \begin{proof} Definujeme\[ S_{n}(m):=\sum_{k=0}^{n-1}k^{m}\] a hledáme tedy hodnotu $S_{n}(m)$. Uvažujme posloupnost $\left(S_{n}(m)\right)_{m=0}^{\infty}$ pro index $m$ (!!) jako posloupnost koeficientů řady s EGF. Postupně upravujeme:\[ \left(S_{n}(m)\right)_{m=0}^{\infty}\xrightarrow{EGF}\sum_{m=0}^{\infty}\frac{S_{n}(m)}{m!}z^{m}=\sum_{m=0}^{\infty}\frac{1}{m!}\left(\sum_{k=0}^{n-1}k^{m}\right)z^{m}=\sum_{k=0}^{n-1}\underbrace{\sum_{m=0}^{\infty}\frac{\left(kz\right)^{m}}{m!}}_{\e^{kz}}=,\] ... napravo máme konečnou geometrickou řadu, kterou můžeme sečíst ...\[ =\e^{0}+\e^{z}+\e^{2z}+...+\e^{(n-1)z}=\frac{\e^{nz}-1}{\e^{z}-1}=\frac{z}{\e^{z}-1}\cdot\frac{\e^{nz}-1}{z}=\] \[ =\left(\sum_{k=0}^{\infty}\frac{B_{k}}{k!}z^{k}\right)\cdot\underbrace{\left(\sum_{i=1}^{\infty}\frac{\left(nz\right)^{i}}{i!}\right)}_{\e^{nz}-1}\frac{1}{z}=\] ... zkrátíme a posuneme indexy ...\[ =\left(\sum_{k=0}^{\infty}\frac{B_{k}}{k!}z^{k}\right)\left(\sum_{i=0}^{\infty}\frac{n^{i+1}z^{i}}{\left(i+1\right)!}\right)=\] ... použijeme vzorec pro násobení mocninných řad, přičemž vnější sčítací index zvolíme jako $m$ ...\[ =\sum_{m=0}^{\infty}\left(\sum_{j=0}^{m}\frac{B_{j}}{j!}\frac{n^{m-j+1}}{\left(m-j+1\right)!}\right)z^{m}=\] ... nakonec vynásobíme $1=\frac{\left(m+1\right)!}{m!\left(m+1\right)}$ a dostaneme ...\[ =\sum_{m=0}^{\infty}\frac{1}{m!}\underbrace{\left(\frac{1}{m+1}\sum_{j=0}^{m}\binom{m+1}{j}B_{j}n^{m-j+1}\right)}_{S_{n}(m)}z^{m}.\] Na konci máme opět mocninnou řadu s EGF a v závorce tak vystupuje právě koeficient $S_{n}(m)$. Platí tedy\[ \sum_{k=0}^{n-1}k^{m}=S_{n}(m)=\frac{1}{m+1}\sum_{j=0}^{m}\binom{m+1}{j}B_{j}n^{m-j+1}.\] \end{proof} \subsubsection{Odhady Bernoulliových čísel} Jak jsme si řekli, řada $\sum_{n=0}^{\infty}\frac{B_{n}}{n!}z^{n}$ má poloměr konvergence $\rho=2\pi$. Podle vzorce z matematické analýzy na výpočet $\rho$ máme tedy\begin{eqnarray*} 2\pi & = & \frac{1}{\limsup\limits _{n\to\infty}\sqrt[n]{\left|\frac{B_{n}}{n!}\right|}},\\ \limsup_{n\to\infty}\sqrt[n]{\left|\frac{B_{n}}{n}\right|} & = & \frac{1}{2\pi}.\end{eqnarray*} S pomocí obou vlastností limes superior% \footnote{\textbf{Připomenutí pojmů z matematické analýzy:} $A\in\R\cup\left\{ \pm\infty\right\} $ je hromadná hodnota reálné posloupnosti $\left(A_{n}\right)$, právě když existuje z ní vybraná posloupnost taková, že $\lim_{n\to\infty}A_{k_{n}}=A$. Každá číselná posloupnost má hromadnou hodnotu. Množina hromadných hodnot posloupnosti má nejmenší a největší prvek. Limes superior je největší hromadná hodnota posloupnosti. Z těchto definic a tvrzení plynou dvě vlastnosti limes superior. $\limsup_{n\to\infty}A_{n}=A$, právě když: \begin{enumerate} \item Pro každé $\varepsilon$ je jen konečně mnoho prvků větších než $A+\varepsilon$, tj. $\left(\forall\varepsilon>0\right)\left(\exists n_{0}\right)\left(\forall n>n_{0}\right)\left(A_{n}<A+\varepsilon\right)$. \item Pro každé $\varepsilon$ existuje nekonečně mnoho prvků větších než $A-\varepsilon$, tj. $\left(\forall\varepsilon>0\right)\left(\exists_{\infty}n\right)\left(A_{n}>A-\varepsilon\right)$. \end{enumerate} % } můžeme odhadnout absolutní hodnotu $B_{n}$ shora i zdola: \begin{enumerate} \item Pro každé $\varepsilon>0$ platí od jistého $n_{0}$ počínaje\begin{eqnarray*} \sqrt[n]{\left|\frac{B_{n}}{n}\right|} & \leq & \frac{1}{2\pi}+\varepsilon,\\ \left|B_{n}\right| & \leq & \left(\frac{1}{2\pi}+\varepsilon\right)^{n}\cdot n!.\end{eqnarray*} \item Pro každé $\varepsilon>0$ platí pro nekonečně mnoho $n$ odhad\[ \left|B_{n}\right|\geq\left(\frac{1}{2\pi}-\varepsilon\right)^{n}\cdot n!.\] \end{enumerate} Ukážeme, že vhodným postupem lze zjistit nejen odhad shora a zdola, ale že lze pro každé $B_{n}$ nalézt i jeho přibližnou hodnotu, tj. číslo, které se mu blíží. Nejprve připomeňme, že funkce komplexní proměnné $f(z)$ má v singulárním bodě $z_{0}$ pól $p$-tého stupně, právě když pro koeficienty jejího Laurentova rozvoje v bodě $z_{0}$ platí $a_{-p}\neq0$ a $a_{n}=0$ pro $n<-p$. To je ekvivalentní s existencí konečné limity\[ \lim_{z\to z_{0}}f(z)\cdot\left(z-z_{0}\right)^{p}\in\C\backslash\left\{ 0\right\} .\] Konkrétně stupeň pólů funkce $f(z)=\frac{z}{\e^{z}-1}$ v bodech $\pm2\pi i$ je $1$, protože pomocí l'Hospitalova pravidla vypočítáme\[ \lim_{z\to2\pi i}\frac{z}{\e^{z}-1}\left(z-2\pi i\right)=\lim_{z\to2\pi i}\frac{z^{2}-2\pi iz}{\e^{z}-1}=\lim_{z\to2\pi i}\frac{2z-2\pi i}{\e^{z}}=2\pi i=a_{-1}=\textrm{Rez}_{2\pi i}\ f.\] Analogicky pro $z\to-2\pi i$ vyjde limita $a_{-1}=-2\pi i$. Má-li však (nějaká) funkce $f$ v bodě $z_{0}$ pól stupně $1$, její Laurentův rozvoj v tomto bodě má tvar\[ f(z)=\frac{a_{-1}}{z-z_{0}}+a_{0}+a_{1}\left(z-z_{0}\right)+...,\] takže funkce $f(z)-\frac{a_{-1}}{z-z_{0}}$ má rozvoj\[ f(z)-\frac{a_{-1}}{z-z_{0}}=a_{0}+a_{1}\left(z-z_{0}\right)+...\] a je tedy holomorfní v bodě $z_{0}$. Z toho plyne, že funkce\[ g(z):=\frac{z}{\e^{z}-1}-\underbrace{\left(\frac{2\pi i}{z-2\pi i}+\frac{-2\pi i}{z+2\pi i}\right)}_{-1.\textrm{ \v{c}leny rozvoje v bodech }\pm2\pi i}\] je holomorfní v bodech $\pm2\pi i$ a tím pádem je holomorfní na kruhu se středem v nule o poloměru $4\pi$, neboť další singulární body funkce $\frac{z}{\e^{z}-1}$ jsou $\pm4\pi i$. Její Laurentův rozvoj v bodě $0$ je rozvojem do mocninné řady s poloměrem konvergence $4\pi$. Tato skutečnost nám umožní získat přibližné hodnoty Bernoulliových čísel. Nejprve upravíme\[ g(z)=\frac{z}{\e^{z}-1}-2\pi i\frac{2\pi i+2\pi i}{z^{2}+4\pi^{2}}=\frac{z}{\e^{z}-1}+\frac{8\pi^{2}}{z^{2}+4\pi^{2}}=\frac{z}{\e^{z}-1}+2\frac{1}{1+\frac{z^{2}}{4\pi^{2}}},\] takže poslední zlomek je ve tvaru součtu geometrické řady s kvocientem $-\frac{z^{2}}{4\pi^{2}}$. Celou funkci $g(z)$ nyní snadno rozvineme do řady, přičemž ještě využijeme, že liché členy posloupnosti $B_{n}$ počínaje $B_{3}$ jsou rovny nule. \[ g(z)=\underbrace{-\frac{1}{2}z}_{\frac{B_{1}}{1!}z^{1}}+\sum_{n=0}^{\infty}\frac{B_{2n}}{\left(2n\right)!}z^{2n}+2\sum_{n=0}^{\infty}\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}z^{2n}=-\frac{1}{2}z+\sum_{n=0}^{\infty}\underbrace{\left(\frac{B_{2n}}{\left(2n\right)!}+2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}\right)}_{a_{2n}}z^{2n}.\] Tato řada má poloměr konvergence $\rho=4\pi$. Nyní odhadneme $B_{n}$ zcela stejným postupem, jako jsme to již jednou udělali. Platí\[ \frac{1}{4\pi}=\limsup_{n\to\infty}\sqrt[n]{\left|a_{n}\right|}=\limsup_{n\to\infty}\sqrt[2n]{\left|a_{2n}\right|}=\limsup_{n\to\infty}\sqrt[2n]{\left|\frac{B_{2n}}{\left(2n\right)!}+2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}\right|}.\] Využijeme jen první vlastnosti limes superior, tj. že pro každé $\varepsilon>0$ platí od jistého $n_{0}$ počínaje\begin{eqnarray*} \sqrt[2n]{\left|\frac{B_{2n}}{\left(2n\right)!}+2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}\right|} & \leq & \frac{1}{4\pi}+\varepsilon,\\ \left|\frac{B_{2n}}{\left(2n\right)!}+2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}\right| & \leq & \left(\frac{1}{4\pi}+\varepsilon\right)^{2n}.\end{eqnarray*} Poslední vztah vlastně odhaduje vzdálenost čísla $\frac{B_{2n}}{\left(2n\right)!}$ od čísla $-2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}$. Proto můžeme napsat\[ \frac{B_{2n}}{\left(2n\right)!}=-2\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}+O\left(\left(\frac{1}{4\pi}+\varepsilon\right)^{2n}\right)\] a definovat posloupnost $C_{2n}$ jako posloupnost přibližných hodnot $B_{2n}$ vztahem\[ C_{2n}=-2\left(2n\right)!\frac{\left(-1\right)^{n}}{\left(4\pi^{2}\right)^{n}}.\] Následující tabulka udává srovnání skutečných hodnot $B_{n}$ a jejich odhadů: \begin{flushleft}\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $2n$& $2$& $4$& $6$& $8$& $10$& $12$& $14$& $16$\tabularnewline \hline $B_{2n}$& $\frac{1}{6}$& $-\frac{1}{30}$& $\frac{1}{42}$& $-\frac{1}{30}$& $\frac{5}{66}$& $-\frac{691}{2730}$& $\frac{7}{6}$& $-\frac{3617}{510}$\tabularnewline \hline $B_{2n}\approx$& $0.16\bar{6}$& $-0.033\bar{3}$& $0.0238$& $-0.0333\bar{3}$& $0.075\overline{75}$& $-0.25311$& $1.16666\bar{6}$& $-7.092156$\tabularnewline \hline $C_{2n}\approx$& $0.10132$& $-0.03079$& $0.0234$& $-0.03319$& $0.07568$& $-0.25305$& $1.166595$& $-7.092048$\tabularnewline \hline \end{tabular}\end{flushleft} \begin{rem*} Posloupnost $C_{2n}$ pro $n\to\infty$ nekonverguje k $B_{2n}$, pro další členy by už rozdíly mezi $B_{2n}$ a $C_{2n}$ rostly. To není překvapením, protože odhad rozdílu je\[ \left(2n\right)!O\left(\left(\frac{1}{4\pi}+\varepsilon\right)^{2n}\right)\xrightarrow{n\to\infty}+\infty.\] Pokud bychom chtěli získat přesnější odhady $B_{2n}$, mohli bychom odečtením potřebných členů vyrobit funkci, kterou lze rozvinout do mocninné řady s poloměrem konvergence $2k\pi>4\pi$. \end{rem*} \subsection{Invertovací formule} \begin{thm} Nechť $\left(a_{n}\right)_{n=0}^{\infty}$, $\left(b_{n}\right)_{n=0}^{\infty}$ jsou dvě posloupnosti, nechť $\forall n\in\N\backslash\left\{ 0\right\} $ je\[ a_{n}=\sum_{k=0}^{n}\binom{n}{k}b_{k}.\] Potom\[ b_{n}=\sum_{k=0}^{n}\binom{n}{k}a_{k}\left(-1\right)^{n-k}.\] \end{thm} \begin{rem*} Je zřejmé, proč se tato věta nazývá invertovací formule. Udává totiž vyjádření členů $b_{n}$ pomocí $a_{n}$ při znalosti vyjádření $a_{n}$ pomocí $b_{n}$. Podobných invertovacích formulí je více. \end{rem*} \begin{proof} Dokázat tuto větu s použitím EGF je snadné. Uvažujme následující EGF:\begin{eqnarray*} \left(a_{n}\right)_{n=0}^{\infty} & \xrightarrow{EGF} & A(z),\\ \left(b_{n}\right)_{n=0}^{\infty} & \xrightarrow{EGF} & B(z).\end{eqnarray*} Podle pravidla (\ref{eq:castec-souc-EGF}) platí\[ \left(\underbrace{\sum_{k=0}^{n}\binom{n}{k}b_{k}}_{a_{n}}\right)\xrightarrow{EGF}e^{z}B(z).\] Dostáváme tedy vztah $A(z)=\e^{z}B(z)$. Zpětně vyjádříme $B(z)=\e^{-z}A(z)$ a provedeme rozvoj funkce $\e^{-z}$ do mocninné řady. Dojdeme tak k rovnosti\[ \sum_{n=0}^{\infty}\frac{\left(-1\right)^{n}}{n!}z^{n}\cdot\sum_{n=0}^{\infty}\frac{a_{n}}{n!}z^{n}=\e^{-z}A(z)=B(z)=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}.\] Vynásobíme řady podle součinového vzorce a získáme\[ \sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{a_{k}}{k!}\frac{\left(-1\right)^{n-k}}{\left(n-k\right)!}\right)z^{n}=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}.\] Porovnáním koeficientů potom dostaneme\begin{eqnarray*} \sum_{k=0}^{n}\frac{a_{k}}{k!}\frac{\left(-1\right)^{n-k}}{\left(n-k\right)!} & = & \frac{b_{n}}{n!},\\ \sum_{k=0}^{n}\binom{n}{k}a_{k}\left(-1\right)^{n-k} & = & b_{n}.\end{eqnarray*} \end{proof} \subsubsection{Použití invertovací formule} Označme $d_{n}$ počet permutací $\pi$ na množině $\left\{ 1,2,...,n\right\} $, které nemají pevný bod, tj. platí pro ně\[ \left(\forall k\in\hat{n}\right)\left(\pi(k)\neq k\right).\] Platí \begin{itemize} \item $d_{1}=0$, \item $d_{2}=1$ (pouze permutace $2,1$), \item $d_{3}=2$ (permutace $2,3,1$ a $3,1,2$). \end{itemize} Snadno se odvodí následující rekurentní vztah.\[ n!=d_{n}+n\cdot d_{n-1}+\binom{n}{2}d_{n-2}+...+\binom{n}{k}d_{n-k}+...+\binom{n}{n-2}d_{2}+\binom{n}{n-1}d_{1}+1.\] Všechny permutace množiny $\hat{n}$ lze totiž rozdělit na permutace bez pevného bodu (těch je $d_{n}$), permutace s jedním pevným bodem (těch je $n\cdot d_{n}$), permutace s dvěma pevnými body atd. Obecně permutací s $k$ pevnými body je $\binom{n}{k}d_{n-k}$, protože pevné body lze vybrat $\binom{n}{k}$ způsoby a zbytek je permutace $n-k$ čísel bez pevného bodu, kterou lze vybrat $d_{n-k}$ způsoby). S použitím rovnosti\[ \binom{n}{k}=\binom{n}{n-k}\] a s dodefinováním $d_{0}:=1$ lze tento vztah upravit na\[ n!=\binom{n}{n}d_{n}+\binom{n}{n-1}d_{n-1}+...+\binom{n}{1}d_{1}+\binom{n}{0}d_{0}=\sum_{k=0}^{n}\binom{n}{k}d_{k}.\] Potom můžeme aplikovat invertovací formuli, takže lze postupně upravovat:\[ d_{n}=\sum_{k=0}^{n}\binom{n}{k}k!\left(-1\right)^{n-k}=n!\sum_{k=0}^{n}\frac{1}{\left(n-k\right)!}\left(-1\right)^{n-k}=n!\sum_{k=0}^{n}\frac{1}{k!}\left(-1\right)^{k}=\] ... využijeme $\sum_{k=0}^{\infty}\frac{1}{k!}\left(-1\right)^{k}=\e^{-1}$ a přepíšeme na ...\[ =n!\left(\e^{-1}-\underbrace{\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!}}_{R}\right).\] Nyní aplikujeme Leibnizovo kritérium, které říká, že zbytek $R$ po alternující řadě je v absolutní hodnotě menší nebo roven než první zanedbaný člen, v našem případě $\frac{1}{\left(n+1\right)!}$. Platí tedy\[ d_{n}=n!\e^{-1}-n!R,\] kde $n!\left|R\right|\leq\frac{1}{n+1}<\frac{1}{2}$ pro $n\geq2$. Lze tedy napsat, že $d_{n}=n!\e^{-1}-\varepsilon,$ kde $\left|\varepsilon\right|<\frac{1}{2}$, neboli $\varepsilon\in(-\frac{1}{2},\frac{1}{2})$. Dále upravíme na $n!\e^{-1}=d_{n}+\varepsilon$, a tedy\[ n!\e^{-1}+\frac{1}{2}=d_{n}+\tilde{\varepsilon},\] kde $\tilde{\varepsilon}\in(0,1)$. Protože $d_{n}\in\N$, tak pokud vezmeme celou část levé i pravé strany této rovnosti, dostaneme explicitní vyjádření pro $d_{n}$:\[ \left[\frac{n!}{\e}+\frac{1}{2}\right]=\left[d_{n}+\tilde{\varepsilon}\right]=d_{n}.\] \subsection{Stirlingova čísla} \begin{defn} Nechť $n\geq k\geq1$. \textbf{Stirlingovo číslo} (druhého druhu)\[ \stirl{n}{k}\] definujeme jako počet rozkladů množiny $\hat{n}$ na $k$ neprázdných podmnožin. \end{defn} \begin{example*} \[ \stirl{4}{2}=7,\] protože rozklady množiny $\left\{ 1,2,3,4\right\} $ na dvě neprázdné podmnožiny mohou být $\boxed{1}\boxed{234}$, $\boxed{2}\boxed{134}$, $\boxed{3}\boxed{124}$, $\boxed{4}\boxed{123}$, $\boxed{12}\boxed{34}$, $\boxed{13}\boxed{24}$, $\boxed{14}\boxed{23}$. \end{example*} \begin{rem} \label{rem:jednoducha-stirl-cisla}Zřejmě $\stirl{n}{1}=1$, $\stirl{n}{n}=1$. Dále \begin{itemize} \item \[ \stirl{n}{2}=\frac{2^{n}-2}{2}=2^{n}-1,\] protože když množinu $\hat{n}$ rozdělujeme na dvě neprázdné podmnožiny, tak z ní vybereme libovolnou podmnožinu kromě $\emptyset$ a $\hat{n}$ (a takových podmnožin je $2^{n}-2$). Druhou podmnožinu pak tvoří zbytek. Výsledný počet dělíme dvěma, neboť na pořadí podmnožin (která je ta první a která ta druhá) nezáleží. \item \[ \stirl{n}{n-1}=\binom{n}{2},\] protože počet rozkladů $\hat{n}$ na $n-1$ neprázdných podmnožin odpovídá počtu dvouprvkových podmnožin $\hat{n}$ (právě jedna podmnožina v rozkladu má totiž dva prvky). \end{itemize} \end{rem} \begin{rem} Je zřejmé, že v rozkladu množiny $\hat{n}$ platí právě jedno z následujících tvrzení: \begin{itemize} \item Buď prvek $n$ tvoří jednoprvkovou podmnožinu, \item nebo prvek $n$ patří do nějaké víceprvkové podmnožiny množiny $\hat{n}$. \end{itemize} Podle této úvahy lze sestavit následující rekurentní vztah:\begin{equation} \stirl{n}{k}=\stirl{n-1}{k-1}+k\stirl{n-1}{k}.\label{eq:stirling-rekurence}\end{equation} $\stirl{n-1}{k-1}$ je totiž počet rozkladů, kde $n$ je ,,zvlášť{}`` v jednoprvkové množině a $k\stirl{n-1}{k}$ je počet rozkladů, kdy $n$ ,,přihodíme{}`` do jedné z $k$ neprázdných podmnožin z rozkladu $\widehat{n-1}$, takže vznikne víceprvková podmnožina. Vzpomeňme si na obdobný vztah, který platí pro kombinační čísla:\[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.\] \end{rem} \begin{defn} \label{def:stirling-extended}Pro $n,k\in\Z$ rozšiřujeme definici Stirlingova čísla takto:\[ \stirl{n}{k}=\begin{cases} 0 & \textrm{pro }n<k\textrm{ nebo }k<0,\\ 0 & \textrm{pro }k=0\textrm{ a }n\neq0,\\ 1 & \textrm{pro }n=k=0.\end{cases}\] V tom případě platí vztah (\ref{eq:stirling-rekurence}) pro každé $n,k\in\Z$ kromě $n=k=0$. \end{defn} Nyní najdeme explicitní vyjádření Stirlingova čísla. Nechť $k\geq0$. Potom definujeme mocninnou řadu\[ B_{k}(x)=\sum_{n\in\Z}\stirl{n}{k}x^{n}\] a naším cílem tedy opět bude najít její koeficienty. Podotkněme, že \begin{enumerate} \item $B_{k}$ je skutečně mocninná řada, protože podle rozšířené definice Stirlingových čísel platí $\sum_{n\in\Z}\stirl{n}{k}x^{n}=\sum_{n=k}^{\infty}\stirl{n}{k}x^{n}$. Rozsah sčítacího indexu $n\in\Z$ však bude velmi šikovný při manipulaci se sumami. \item Opět podle definice \ref{def:stirling-extended} platí $B_{0}(x)=1$. \end{enumerate} Nyní použijeme rovnost (\ref{eq:stirling-rekurence}) a dosadíme do definice $B_{k}$. Přitom s výhodou využíváme rozsah indexu $n\in\Z$.\[ B_{k}(x)=x\sum_{n\in\Z}\stirl{n-1}{k-1}x^{n-1}+kx\sum_{n\in\Z}\stirl{n-1}{k}x^{n-1}=xB_{k-1}(x)+kxB_{k}(x).\] Z toho vyjádříme\[ B_{k}(x)=\frac{x}{1-kx}B_{k-1}(x)\] a postupným dosazováním $B_{k-1}(x)$, $B_{k-2}(x)$,... dostaneme\[ B_{k}(x)=\frac{x}{1-kx}\cdot\frac{x}{1-(k-1)x}\cdot\frac{x}{1-(k-2)x}\cdots\frac{x}{1-2x}\frac{x}{1-x}\cdot\underbrace{1}_{B_{0}(x)}.=\frac{x^{k}}{(1-x)(1-2x)\cdots(1-kx)}.\] Jestliže tuto (generující) funkci rozvineme do mocninné řady, tak koeficient u $x^{n}$ bude díky jednoznačnosti rozvoje právě $\stirl{n}{k}$. Abychom byli schopni rozvoj provést, rozložíme nejprve funkci $B_{k}(x)/x^{k}$ na parciální zlomky. Obecně má tento rozklad tvar\begin{equation} \frac{1}{(1-x)(1-2x)\cdots(1-kx)}=\frac{\alpha_{1}}{1-x}+\frac{\alpha_{2}}{1-2x}+...+\frac{\alpha_{k}}{1-kx}.\label{eq:stirl-parc-zlomky}\end{equation} Nyní je třeba nalézt koeficienty $\alpha_{j}$. Zvolme si konkrétní $j\in\hat{k}$. Rovnost (\ref{eq:stirl-parc-zlomky}) vynásobíme výrazem $(1-jx)$ a poté dosadíme $x=\frac{1}{j}$. Dostaneme\begin{eqnarray*} \left.\frac{1}{(1-x)(1-2x)\cdots(1-(j-1)x)(1-(j+1)x)\cdots(1-kx)}\right|_{x=\frac{1}{j}} & = & \alpha_{j},\\ \frac{1}{\left(1-\frac{1}{j}\right)\left(1-\frac{2}{j}\right)\cdots\left(1-\frac{j-1}{j}\right)\left(1-\frac{j+1}{j}\right)\cdots\left(1-\frac{k}{j}\right)} & = & \alpha_{j}.\end{eqnarray*} Pokud nyní rozšíříme zlomek nalevo výrazem $j^{k-1}$ tak, že každou závorku ve jmenovateli vynásobíme $j$, dostaneme\[ \frac{j^{k-1}}{\underbrace{(j-1)(j-2)\cdots2\cdot1}_{\left(j-1\right)!}\cdot\underbrace{(-1)\cdot(-2)\cdots(j-k)}_{\left(k-j\right)!\left(-1\right)^{k-j}}}=\frac{j^{k}\left(-1\right)^{k-j}}{j!\left(k-j\right)!}=\alpha_{j}.\] Koeficienty $\alpha_{j}$ jsme tedy získali. Rozvoje jednotlivých zlomků $\frac{1}{1-jx}$ jsou přitom snadné, jedná se totiž o součty geometrických řad s kvocienty $jx$. Celý rozvoj $B_{k}(x)$ tedy je\[ B_{k}(x)=x^{k}\sum_{j=1}^{k}\alpha_{j}\sum_{n=0}^{\infty}\left(jx\right)^{n}.\] Nyní zaměníme pořadí sum, dosadíme hodnoty $\alpha_{j}$ a dostaneme\[ B_{k}(x)=\sum_{n=0}^{\infty}\sum_{j=1}^{k}\frac{j^{k}\left(-1\right)^{k-j}}{j!\left(k-j\right)!}j^{n}x^{n+k}.\] Koeficient u $x^{n}$ je tedy\[ \stirl{n}{k}=\sum_{j=1}^{k}\frac{j^{k}\left(-1\right)^{k-j}}{j!\left(k-j\right)!}j^{n-k}=\sum_{j=1}^{k}\frac{j^{n}\left(-1\right)^{k-j}}{j!\left(k-j\right)!}=\sum_{j=0}^{k}\frac{j^{n}\left(-1\right)^{k-j}}{j!\left(k-j\right)!}.\] \begin{rem*} Explicitní vzorec pro $\stirl{n}{k}$ byl odvozen za použití rozšířené definice \ref{def:stirling-extended}, a proto tuto definici splňuje. Jen pro zajímavost tak například víme, že\[ \stirl{13}{19}=0=\sum_{j=1}^{19}\frac{j^{13}\left(-1\right)^{19-j}}{j!\left(19-j\right)!}.\] \end{rem*} \subsection{Bellova čísla} \begin{defn} Pro $n\in\N_{0}$ definujeme \textbf{Bellovo číslo} $b_{n}$ jako\[ b_{n}:=\sum_{k\geq0}\stirl{n}{k}.\] \end{defn} \begin{rem*} Platí $b_{0}=1$ a pro $n>0$ je\[ b_{n}:=\sum_{k\geq1}\stirl{n}{k}\] rovno počtu různých relací ekvivalence, které mohou existovat na $n$-prvkové množině. To je zřejmé, protože každá ekvivalence rozděluje $n$-prvkovou množinu na třídy ekvivalence, tj. na nějaký počet ($k$) neprázdných podmnožin. \end{rem*} \begin{example} \label{exa:b4}Počet různých ekvivalencí na $4$-prvkové množině je $15$. Podle poznámky \ref{rem:jednoducha-stirl-cisla} umíme totiž vypočítat\[ b_{4}=\stirl{4}{1}+\stirl{4}{2}+\stirl{4}{3}+\stirl{4}{4}=1+7+6+1=15.\] \end{example} Podívejme se, jak dokážeme vyjádřit $b_{n}$ po dosazení explicitního vzorce pro $\stirl{n}{k}$. Platí\[ b_{n}=\sum_{k\geq0}\stirl{n}{k}=\sum_{k=0}^{\infty}\stirl{n}{k}=\sum_{k=0}^{\infty}\sum_{j=0}^{k}\underbrace{\frac{j^{n}}{j!}}_{a_{j}}\cdot\underbrace{\frac{\left(-1\right)^{k-j}}{\left(k-j\right)!}}_{b_{k-j}}=\] ... použijeme pravidlo pro součin mocninných řad ...\[ =\left(\sum_{j=1}^{\infty}\frac{j^{n}}{j!}\right)\left(\sum_{l=0}^{\infty}\frac{\left(-1\right)^{l}}{l!}\right)=\frac{1}{\e}\sum_{j=1}^{\infty}\frac{j^{n}}{j!}=\frac{1}{\e}\sum_{j=0}^{\infty}\frac{j^{n}}{j!}=b_{n}.\] Tento tvar $b_{n}$ se nám bude hodit v následující větě. \begin{thm} \label{thm:bellova-cisla-EGF}Označme\[ B(z):=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}.\] Potom platí\[ B(z)=\e^{\e^{z}-1},\] tj.\[ \left(b_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}B(z)=\e^{\e^{z}-1}.\] \end{thm} \begin{proof} Do definice $B(z)$ dosadíme právě vypočítanou hodnotu $b_{n}$ a upravujeme.\[ B(z)=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}=\frac{1}{\e}\sum_{n=0}^{\infty}\frac{1}{n!}\underbrace{\sum_{j=0}^{\infty}\frac{j^{n}}{j!}z^{n}}_{(*)}=\frac{1}{\e}\sum_{j=0}^{\infty}\frac{1}{j!}\sum_{n=0}^{\infty}\frac{j^{n}}{n!}z^{n}=\] \[ =\frac{1}{\e}\sum_{j=0}^{\infty}\frac{1}{j!}\underbrace{\sum_{n=0}^{\infty}\frac{\left(jz\right)^{n}}{n!}}_{\e^{jz}}=\frac{1}{\e}\sum_{j=0}^{\infty}\frac{1}{j!}\left(\e^{z}\right)^{j}=\frac{1}{\e}\e^{\e^{z}}=\e^{\e^{z}-1}.\] Poznamenejme, že výsledek je konečné číslo. To spolu s konečností sumy $(*)$ ospravedlňuje záměnu sum v prvním řádku. \end{proof} Pomocí předchozí věty odvodíme rekurentní vztah pro výpočet $b_{n}$. Vyjdeme ze vztahu\[ \e^{\e^{z}-1}=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n},\] který zlogaritmujeme a následně zderivujeme:\begin{eqnarray*} \e^{z}-1 & = & \ln\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n},\\ \e^{z} & = & \frac{\sum\limits _{n=1}^{\infty}\frac{b_{n}}{\left(n-1\right)!}z^{n-1}}{\sum\limits _{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}}.\end{eqnarray*} Nyní vyjádříme $\e^{z}=\sum_{n=0}^{\infty}\frac{z^{n}}{n!}$ a vynásobíme jmenovatelem:\[ \left(\sum_{n=0}^{\infty}\frac{b_{n}}{n!}z^{n}\right)\left(\sum_{n=0}^{\infty}\frac{1}{n!}z^{n}\right)=\sum_{n=0}^{\infty}\frac{b_{n+1}}{n!}z^{n}.\] Použijeme vzorec pro násobení mocninných řad:\[ \sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{b_{k}}{k!}\cdot\frac{1}{\left(n-k\right)!}\right)z^{n}=\sum_{n=0}^{\infty}\frac{b_{n+1}}{n!}z^{n}.\] Nakonec porovnáme koeficienty u obou mocninných řad. Platí tedy\begin{eqnarray*} \frac{b_{n+1}}{n!} & = & \sum_{k=0}^{n}\frac{b_{k}}{k!}\cdot\frac{1}{\left(n-k\right)!},\\ b_{n+1} & = & \sum_{k=0}^{n}\binom{n}{k}b_{k}.\end{eqnarray*} \begin{example*} \begin{eqnarray*} b_{0} & = & 1\\ b_{1} & = & \binom{0}{0}\cdot b_{0}=1\cdot1=1\\ b_{2} & = & \binom{1}{0}\cdot b_{0}+\binom{1}{1}\cdot b_{1}=1\cdot1+1\cdot1=2\\ b_{3} & = & \binom{2}{0}\cdot b_{0}+\binom{2}{1}\cdot b_{1}+\binom{2}{2}\cdot b_{2}=1\cdot1+2\cdot1+1\cdot2=5\\ b_{4} & = & \binom{3}{0}\cdot b_{0}+\binom{3}{1}\cdot b_{1}+\binom{3}{2}\cdot b_{2}+\binom{3}{3}\cdot b_{3}=1\cdot1+3\cdot1+3\cdot2+1\cdot5=15.\end{eqnarray*} Číslo $b_{4}$ jsme již vypočítali z definice pomocí Stirlingových čísel v příkladu \ref{exa:b4}. \end{example*} \begin{rem} \label{rem:explicitni-vzorec-pro-b-n}Víme, že $b_{n}$ je počet ekvivalencí na množině $\hat{n}$. Následující kombinatorickou úlohou je možné získat explicitní vzorec pro výpočet $b_{n}$. Uvažujme ekvivalence provádějících rozklad $\hat{n}$ na $k$ tříd. Nechť tyto třídy mají $l_{1},l_{2},...,l_{k}$ prvků, přičemž samozřejmě $l_{j}\geq1$ a $\sum_{j=1}^{k}l_{j}=n$. Počet takových ekvivalencí je\[ \frac{1}{k!}\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-2}l_{j}}{l_{k-1}}\underbrace{\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}}}_{\binom{l_{k}}{l_{k}}=1},\] což je celkem zřejmé. Člen $\frac{1}{k!}$ vyjadřuje, že na pořadí (postupného) výběru tříd ekvivalence nezáleží. Počet všech ekvivalencí s $k$ třídami je tedy\[ \sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\frac{1}{k!}\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-2}l_{j}}{l_{k-1}}\] a celkový počet ekvivalencí je potom zřejmě\[ b_{n}=\sum_{k=1}^{n}\sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\frac{1}{k!}\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-2}l_{j}}{l_{k-1}}.\] Jak je vidět, pro výpočet $b_{n}$ se tento vzorec nehodí. S jeho pomocí bychom však byli schopni dokázat větu \ref{thm:bellova-cisla-EGF}, pokud bychom využili \emph{skládání generujících funkcí}. \end{rem} \subsection{Skládání generujících funkcí} Mějme mocninné řady s EGF\begin{eqnarray*} F(z) & = & \frac{f_{0}}{0!}+\frac{f_{1}}{1!}z+\frac{f_{2}}{2!}z^{2}+...,\\ G(z) & = & \frac{g_{0}}{0!}+\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\end{eqnarray*} a zajímejme se, jakou posloupností je určena řada se složenou exponenciální generující funkcí $F(G(z))$. Pokud dosadíme z právě rozepsaných vztahů, dostaneme \[ F(G(z))=\frac{f_{0}}{0!}+\frac{f_{1}}{1!}\left(\frac{g_{0}}{0!}+\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)+\frac{f_{2}}{2!}\left(\frac{g_{0}}{0!}+\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)^{2}+....\] V této (zřejmě opět) mocninné řadě bychom tedy chtěli získat koeficient u $z^{n}$. Nejprve si uvědomíme, že už nultý koeficient (u $z^{0}$) je nekonečná číselná řada\[ \frac{f_{0}}{0!}+\frac{f_{1}}{1!}\frac{g_{0}}{0!}+\frac{f_{2}}{2!}\left(\frac{g_{0}}{0!}\right)^{2}+...\] a volbou hodnoty proměnné $z$ nelze ovlivnit její konvergenci. Proto v následujícím uvažujeme pouze takové EGF, pro něž $g_{0}=0$. Koeficient u $z^{0}$ je potom zřejmě $\frac{f_{0}}{0!}=f_{0}$. Abychom získali koeficient u $z^{n}$ \fbox{pro $n\geq1$}, uvažme, že nejmenší mocnina v každé závorce je $z$ a závorky jsou postupně umocňovány na $0,1,2,3,...$. V každém členu\[ \frac{f_{k}}{k!}\cdot\left(\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)^{k}\] je tedy nejmenší mocnina po roznásobení $z^{k}$. Z toho plyne, že koeficient u $z^{n}$ můžeme hledat roznásobováním pouze prvních $n$ závorek, vyšší mocniny na něj nemají vliv. Vezměme si znovu $k$-tý člen součinové řady, tj. člen\[ \frac{f_{k}}{k!}\cdot\left(\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)^{k}=\frac{f_{k}}{k!}\cdot\underbrace{\left(\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)\cdot\left(\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)\cdots\left(\frac{g_{1}}{1!}z+\frac{g_{2}}{2!}z^{2}+...\right)}_{k\textrm{-krát}}.\] Aby v nějakém členu po roznásobení závorek vzniklo $z^{n}$, musí se $\forall j\in\hat{k}$ mezi sebou násobit členy ($j$-tý člen pochází z $j$-té závorky)\[ \frac{g_{l_{j}}}{l_{j}!}z^{l_{j}},\] pro něž platí\[ \sum_{j=1}^{k}l_{j}=1\] a samozřejmě $l_{j}\geq1$. Koeficient u $z^{n}$ vznikne jako součet součinů přes všechny možné výběry členů v jednotlivých závorkách. Tento koeficient je tedy roven\[ \tilde{h}_{n}=\underbrace{\sum_{k=1}^{n}}_{\textrm{suma p\v{r}es }n\textrm{ prvních \v{c}len\r{u}}}\frac{f_{k}}{k!}\cdot\underbrace{\sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\frac{g_{l_{1}}}{l_{1}!}\cdot\frac{g_{l_{2}}}{l_{2}!}\cdots\frac{g_{l_{k}}}{l_{k}!}}_{\textrm{koeficient vzniklý z }k\textrm{-tého \v{c}lenu}}.\] Podle definice EGF je\[ \left(a_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}\sum_{n=0}^{\infty}\frac{a_{n}}{n!}z^{n},\] takže můžeme shrnout\[ \left(h_{n}\right)_{n=0}^{\infty}=\left(n!\tilde{h}_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}F(G(z)).\] Nyní dosadímě $h_{n}=n!\tilde{h}_{n}$ a použijeme rovnost\[ \frac{n!}{l_{1}!l_{2}!\cdots l_{k}!}=\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}},\] kterou lze snadno ověřit. Dostaneme tak konečně vyjádření koeficientů posloupnosti příslušné generující funkci $F(G(z))$: \begin{equation} h_{n}=\sum_{k=1}^{n}\frac{f_{k}}{k!}\sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}}\prod_{j=1}^{k}g_{l_{j}}.\label{eq:koeficienty_slozene_gf}\end{equation} \begin{example*} Vraťme se nyní k poznámce \ref{rem:explicitni-vzorec-pro-b-n}. Uvažujme mocninné řady\begin{eqnarray*} \left(1\right)_{n=0}^{\infty} & \xrightarrow{EGF} & F(z)=\sum_{n=0}^{\infty}\frac{1}{n!}z^{n}=\e^{z},\\ \left(1\right)_{n=1}^{\infty} & \xrightarrow{EGF} & G(z)=\sum_{n=1}^{\infty}\frac{1}{n!}z^{n}=\e^{z}-1.\end{eqnarray*} Potom exponenciální generující funkce $F(G(z))=\e^{\e^{z}-1}$ má podle (\ref{eq:koeficienty_slozene_gf}) koeficienty\[ b_{n}=\sum_{k=1}^{n}\frac{1}{k!}\sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-2}l_{j}}{l_{k-1}},\] tedy přímo Bellova čísla. Tím jsme alternativním způsobem dokázali větu \ref{thm:bellova-cisla-EGF}. \end{example*} \begin{example} Určete $d_{n}:=$počet $2$-regulárních% \footnote{$G=(V,E)$ je $r$-regulární, právě když $\left(\forall v\in V\right)\left(d_{G}(v)=r\right)$.% } grafů na $n$ vrcholech. Najdeme jednoduchý rekurentní vztah pro výpočet $d_{n}$. Řešení se bude skládat ze tří kroků: \begin{enumerate} \item Z kombinatorické úvahy sestavíme složitý explicitní vzorec pro výpočet $d_{n}$. \item Vzorec upravíme na tvar odpovídající tvaru členu posloupnosti, která přísluší určité složené EGF, a tuto EGF vypočítáme. \item Podobně jako u Bellových čísel z EGF odvodíme rekurentní vztah. \end{enumerate} \textbf{Krok 1.} Lze si snadno rozmyslet, že $2$-regulární graf je právě takový, který vznikne jako disjunktní sjednocení určitého počtu kružnic. Nejprve nalezněme počet grafů na $n$ vrcholech, které jsou disjunktním sjednocením právě $k$ kružnic. Každá kružnice má minimálně $3$ vrcholy. Konkrétně tedy máme kružnice délek $l_{1},l_{2},...,l_{k}$, přičemž $\sum_{j=1}^{k}l_{j}=n$ a $\left(\forall j\in\hat{k}\right)\left(l_{j}\geq3\right)$. Chceme-li spočítat počet různých kružnic na $l$ vrcholech $v_{1},...,v_{l}$, zafixujeme vrchol $v_{1}$, z něhož kružnice začíná a do nějž se opět vrací. Ostatní vrcholy mohou být v libovolné z $\left(l-1\right)!$ permutací. Na orientaci kružnice však nezáleží, takže na konkrétních $l$ vrcholech existuje $\frac{\left(l-1\right)!}{2}$ různých kružnic. Počet grafů na $n$ vrcholech, které jsou sjednocením právě $k$ kružnic, tedy je\[ \frac{1}{k!}\sum_{\substack{l_{j}\geq3,\ j\in\hat{k}\\ \sum l_{j}=n} }\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}}\cdot\frac{\left(l_{1}-1\right)!}{2}\cdot\frac{\left(l_{2}-1\right)!}{2}\cdots\frac{\left(l_{k}-1\right)!}{2},\] přičemž kombinační čísla odpovídají počtu způsobů výběru $l_{j}$ vrcholů pro jednotlivé kružnice a zlomek $\frac{1}{k!}$ vyjadřuje, že nezávisí na pořadí těchto kružnic. $d_{n}$ je pak součet uvedených výrazů pro všechna přípustná $k$:\[ d_{n}=\sum_{k=1}^{\left[\frac{n}{3}\right]}\frac{1}{k!}\sum_{\substack{l_{j}\geq3,\ j\in\hat{k}\\ \sum l_{j}=n} }\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}}\cdot\prod_{j=1}^{k}\frac{\left(l_{j}-1\right)!}{2}.\] \textbf{Krok 2.} Abychom dostali vzorec pro $d_{n}$ do tvaru odpovídajícího $n$-tému koeficientu řady s EGF, definujeme\[ g_{n}=\begin{cases} \frac{\left(n-1\right)!}{2} & \textrm{pro }n\geq3,\\ 0 & \textrm{pro }n\in\left\{ 0,1,2\right\} .\end{cases}\] Potom\[ d_{n}=\sum_{k=1}^{n}\frac{1}{k!}\sum_{\substack{l_{j}\geq1,\ j\in\hat{k}\\ \sum l_{j}=n} }\binom{n}{l_{1}}\binom{n-l_{1}}{l_{2}}\binom{n-l_{1}-l_{2}}{l_{3}}\cdots\binom{n-\sum_{j=1}^{k-1}l_{j}}{l_{k}}\cdot\prod_{j=1}^{k}g_{l_{j}},\] protože \begin{enumerate} \item Je jasné, že je-li $k>\left[\frac{n}{3}\right]$, tak jedno z $l_{1},...,l_{k}$ bude $l_{j}<3$, takže $g_{l_{j}}=0$. Lze tedy brát $k$ od jedné až do $n$. \item Protože $l_{j}<3\Rightarrow g_{l_{j}}=0$, není nutné uvažovat podmínku $l_{j}\geq3$. \end{enumerate} Z tvaru $d_{n}$, který již odpovídá (\ref{eq:koeficienty_slozene_gf}), jsme schopni vyjádřit členy posloupností $\left(f_{n}\right),\left(g_{n}\right)$, které přísluší řadám s generujícími funkcemi $F$ a $G$. Připomeňme však, že vztah (\ref{eq:koeficienty_slozene_gf}) platí pouze pro $n\geq1$ a na nultý koeficient $d_{0}=f_{0}$ zde dosud nemáme žádnou podmínku. $\left(d_{n}\right)_{n=0}^{\infty}$ tedy přísluší exponenciální generuící funkci, která vznikne složením\[ \left(f_{n}\right)_{n=0}^{\infty}=\left(1\right)_{n=0}^{\infty}\xrightarrow{EGF}F(z)=\e^{z},\] přičemž jsme definovali $d_{0}=f_{0}=1$, a\[ \left(g_{n}\right)_{n=0}^{\infty}\xrightarrow{EGF}G(z)=\sum_{n=0}^{\infty}\frac{g_{n}}{n!}z^{n}.\] Zbývá vypočítat $G(z)$. Dosadíme z definice $\left(g_{n}\right)$ a dostaneme\[ G(z)=\sum_{n=0}^{\infty}\frac{g_{n}}{n!}z^{n}=\sum_{n=3}^{\infty}\frac{\left(n-1\right)!}{2n!}z^{n}=\frac{1}{2}\sum_{n=3}^{\infty}\frac{z^{n}}{n}=\] ... derivací této řady je však geometrická řada, jejíž součet známe ...\[ =\frac{1}{2}\int\limits _{0}^{z}\left(\underbrace{\sum_{n=3}^{\infty}t^{n-1}}_{=t^{2}\frac{1}{1-t}=-1-t+\frac{1}{1-t}}\right)\dd t=\frac{1}{2}\left(-z-\frac{z^{2}}{2}-\ln\left|1-z\right|\right).\] Generující funkce příslušná $\left(d_{n}\right)_{n=0}^{\infty}$ je tedy\[ F(G(z))=\e^{-\frac{z}{2}-\frac{z^{2}}{4}-\frac{1}{2}\ln\left|1-z\right|}=\frac{1}{\sqrt{1-z}}\cdot\e^{-\frac{z}{2}-\frac{z^{2}}{4}}.\] \textbf{Krok 3.} Nyní z $F(G(z))$ získáme rekurentní vztah pro $d_{n}$ stejně jako u Bellových čísel. Platí rovnost\[ \sum_{n=0}^{\infty}\frac{d_{n}}{n!}z^{n}=\frac{1}{\sqrt{1-z}}\cdot\e^{-\frac{z}{2}-\frac{z^{2}}{4}},\] kterou zlogaritmujeme a zderivujeme:\begin{eqnarray*} \ln\sum_{n=0}^{\infty}\frac{d_{n}}{n!}z^{n} & = & -\frac{z}{2}-\frac{z^{2}}{4}-\frac{1}{2}\ln\left(1-z\right),\\ \frac{\sum\limits _{n=1}^{\infty}\frac{d_{n}}{\left(n-1\right)!}z^{n-1}}{\sum\limits _{n=0}^{\infty}\frac{d_{n}}{n!}z^{n}} & = & -\frac{1}{2}-\frac{z}{2}+\frac{1}{2\left(1-z\right)}=-\frac{1}{2}-\frac{z}{2}+\frac{1}{2}\sum_{n=0}^{\infty}z^{n}=\frac{1}{2}\sum_{n=2}^{\infty}z^{n}.\end{eqnarray*} Opět vynásobíme jmenovatelem a následně použijeme vzorec pro součin mocninných řad:\[ \sum\limits _{n=1}^{\infty}\frac{d_{n}}{\left(n-1\right)!}z^{n-1}=\frac{1}{2}\left(\sum_{n=2}^{\infty}z^{n}\right)\left(\sum\limits _{n=0}^{\infty}\frac{d_{n}}{n!}z^{n}\right)=\frac{1}{2}\left(\sum\limits _{n=0}^{\infty}\frac{d_{n}}{n!}z^{n}\right)\left(\sum_{n=0}^{\infty}z^{n+2}\right)=\] \[ =\frac{1}{2}\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{d_{k}}{k!}z^{n+2}.\] Nakonec porovnáme koeficienty u $z^{n-1}$:\begin{eqnarray*} \frac{d_{n}}{\left(n-1\right)!} & = & \frac{1}{2}\sum_{k=0}^{n-3}\frac{d_{k}}{k!},\\ d_{n} & = & \frac{\left(n-1\right)!}{2}\sum_{k=0}^{n-3}\frac{d_{k}}{k!}.\end{eqnarray*} Výsledek si můžeme ověřit na prvních čtyřech členech posloupnosti. Z hlavy víme\[ d_{0}=1,d_{1}=d_{2}=0,d_{3}=1,d_{4}=3\] a podle našeho rekurentního vztahu je\[ d_{4}=\frac{3!}{2}\left(\frac{d_{0}}{0!}+\frac{d_{1}}{1!}\right)=\frac{6}{2}\left(\frac{1}{1}+\frac{0}{1}\right)=3.\] \end{example}