Součásti dokumentu 01ZTGA
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}
