Endliche Mengen/Surjektive Abbildungen/Siebformel/Fakt/Beweis

Beweis

Wir setzen ${}B=\{1,\ldots ,k\}$. Zu ${}j=1,\ldots ,k$ setzen wir

${}F_{j}={\left\{f:A\rightarrow B\mid j{\text{ wird nicht getroffen unter }}f\right\}}\,.$

Die Menge der nichtsurjektiven Abbildungen ist somit ${}F=\bigcup _{j=1}^{k}F_{j}$. Zu ${}C\subseteq B$ haben die Durchschnitte

${}F_{C}=\bigcap _{j\in C}F_{j}\,$

eine inhaltliche Bedeutung: Es handelt sich um alle Funktionen von ${}A$ nach ${}B\setminus C$. Deren Anzahl ist nach Fakt gleich ${}(k-j)^{n}$. Nach der Siebformel ist somit

${}{\begin{aligned}{\#\left(F\right)}&=\sum _{j=1}^{k}(-1)^{j+1}{\left(\sum _{C\subseteq \{1,\ldots ,k\},\,{\#\left(C\right)}=j}{\#\left(F_{C}\right)}\right)}\\&=\sum _{j=1}^{k}(-1)^{j+1}{\binom {k}{j}}(k-j)^{n}\\&=\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}$

Die Anzahl der surjektiven Abbildungen ist daher gleich

${}{\begin{aligned}k^{n}-{\left(\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}\right)}&=k^{n}+\sum _{\ell =0}^{k-1}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}\\&=\sum _{\ell =0}^{k}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}$

Zur bewiesenen Aussage