Endliche Mengen/Surjektive Abbildungen/Produktpotenzen/Summe/Fakt/Beweis

Beweis

Wir führen Induktion über ${}k$ und bei fixiertem ${}k$ Induktion nach ${}n$. Bei ${}k=0$ ist die Aussage richtig. Es sei also ${}k$ fixiert und sei die Aussage für alle kleineren ${}k$ und alle ${}n$ bereits bewiesen. Für ${}n<k$ ist der Summenausdruck gleich ${}0$, und es gibt auch keine surjektive Abbildung einer ${}n$-elementigen Menge in eine größere Menge. Bei ${}n=k$ ist das einzige Indextupel gleich ${}(1,\ldots ,1)$ und der Summenausdruck ist gleich ${}k!$, was mit der Anzahl der surjektiven bzw. bijektiven Abbildungen nach Fakt übereinstimmt. Es sei also die Aussage für ${}n\geq k$ bewiesen und betrachten wir eine surjektive Abbildung ${}f$ von ${}{\{1,\ldots ,n+1\}}$ nach ${}\{1,\ldots ,k\}$. Dabei ist entweder schon die Einschränkung ${}g$ auf ${}{\{1,\ldots ,n\}}$ surjektiv oder nicht. Im ersten Fall gibt es bei gegebenem ${}g$ genau ${}k$ Möglichkeiten für ${}f$, da ja ${}n+1$ auf eines der ${}k$ Elemente abgebildet werden kann. Im zweiten Fall, wenn ${}g$ nicht surjektiv ist, so wird durch ${}g$ genau ein Element der Bildmenge nicht getroffen, und ${}f$ muss ${}n+1$ auf dieses nicht getroffene Element abbilden, um die Surjektivität sicherzustellen. Es gibt hierbei ${}k$ Möglichkeiten, welches Element von ${}g$ nicht getroffen wird. Ferner ist ${}g$ eine surjektive Abbildung auf eine ${}k-1$-elementige Teilmenge. Somit ist unter Verwendung der Induktionsvoraussetzung die Anzahl der surjektiven Abbildungen von ${}{\{1,\ldots ,n+1\}}$ nach ${}\{1,\ldots ,k\}$ gleich

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

Zur bewiesenen Aussage