Beweis
Wir führen Induktion über
und bei fixiertem
Induktion nach
. Bei
ist die Aussage richtig. Es sei also
fixiert und sei die Aussage für alle kleineren
und alle
bereits bewiesen. Für
ist der Summenausdruck gleich
, und es gibt auch keine surjektive Abbildung einer
-elementigen Menge in eine größere Menge. Bei
ist das einzige Indextupel gleich
und der Summenausdruck ist gleich
, was mit der Anzahl der surjektiven bzw. bijektiven Abbildungen nach
Fakt
übereinstimmt. Es sei also die Aussage für
bewiesen und betrachten wir eine surjektive Abbildung
von
nach
. Dabei ist entweder schon die Einschränkung
auf
surjektiv oder nicht. Im ersten Fall gibt es bei gegebenem
genau
Möglichkeiten für
, da ja
auf eines der
Elemente abgebildet werden kann. Im zweiten Fall, wenn
nicht surjektiv ist, so wird durch
genau ein Element der Bildmenge nicht getroffen, und
muss
auf dieses nicht getroffene Element abbilden, um die Surjektivität sicherzustellen. Es gibt hierbei
Möglichkeiten, welches Element von
nicht getroffen wird. Ferner ist
eine surjektive Abbildung auf eine
-elementige Teilmenge. Somit ist unter Verwendung der Induktionsvoraussetzung die Anzahl der surjektiven Abbildungen von
nach
gleich
![{\displaystyle {}{\begin{aligned}\,&={\#\left({\left\{f:{\{1,\ldots ,n+1\}}\rightarrow \{1,\ldots ,k\}\mid f{|}_{\{1,\ldots ,n\}}{\text{ surjektiv}}\right\}}\right)}+{\#\left({\left\{f:{\{1,\ldots ,n+1\}}\rightarrow \{1,\ldots ,k\}\mid f{|}_{\{1,\ldots ,n\}}{\text{ nicht surjektiv}}\right\}}\right)}\\&=k\cdot \sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}+k\cdot \sum _{(b_{1},\ldots ,b_{k-1}):\,b_{1}+b_{2}+\cdots +b_{k-1}=n,\,b_{j}\geq 1}1^{b_{1}}2^{b_{2}}\cdots (k-1)^{b_{k-1}}\\&=\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k-1}+a_{k}+1=n+1,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}+1}+\sum _{(b_{1},\ldots ,b_{k-1}):\,b_{1}+b_{2}+\cdots +b_{k-1}+1=n+1,\,b_{j}\geq 1}1^{b_{1}}2^{b_{2}}\cdots (k-1)^{b_{k-1}}\cdot k^{1}\\&=\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1,\,c_{k}\geq 2}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}+\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1,\,c_{k}=1}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}\\&=\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f7c1f46eaeecd3a5a5ecf5e0060fec3819d428b)