Endliche Mengen/Surjektive Abbildungen/Siebformel/Fakt/Beweis

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

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

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

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

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

${\displaystyle {}{\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

${\displaystyle {}{\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}}}$