Endliche Mengen/Surjektive Abbildungen/Potenzprodukte/Summe/Fakt/Beweis2

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$ (zu diesen kleineren $k$) 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,\dots ,1)$ und der Summenausdruck ist gleich $k!$, was mit der Anzahl der surjektiven bzw. bijektiven Abbildungen nach Fakt übereinstimmt. Es sei also die Aussage auch für ein  $n\ge k$  bewiesen; wir betrachten eine surjektive Abbildung $f$ von $\{1,\dots ,n+1\}$ nach $\{1,\dots ,k\}$. Dabei ist entweder schon die Einschränkung $g$ auf $\{1,\dots ,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,\dots ,n+1\}$ nach $\{1,\dots ,k\}$ gleich

$\begin{array}{cc}& =\mathrm{\#}\left(\{f:\{1,\dots ,n+1\}\to \{1,\dots ,k\}\mid f{|}_{\{}1,\dots ,n\}\text{ surjektiv}\}\right)+\mathrm{\#}\left(\{f:\{1,\dots ,n+1\}\to \{1,\dots ,k\}\mid f{|}_{\{}1,\dots ,n\}\text{ nicht surjektiv}\}\right)\\ \\ & =k\cdot \sum _{(a_1,\dots ,a_k):a_1+a_2+\cdots +a_k=n,a_j\ge 1}{1}^{a_1}{2}^{a_2}\cdots k^{a_k}+k\cdot \sum _{(b_1,\dots ,b_{k-1}):b_1+b_2+\cdots +b_{k-1}=n,b_j\ge 1}{1}^{b_1}{2}^{b_2}\cdots (k-1{)}^{b_{k-1}}\\ & =\sum _{(a_1,\dots ,a_k):a_1+a_2+\cdots +a_{k-1}+a_k+1=n+1,a_j\ge 1}{1}^{a_1}{2}^{a_2}\cdots k^{a_k+1}+\sum _{(b_1,\dots ,b_{k-1}):b_1+b_2+\cdots +b_{k-1}+1=n+1,b_j\ge 1}{1}^{b_1}{2}^{b_2}\cdots (k-1{)}^{b_{k-1}}\cdot k^1\\ & =\sum _{(c_1,\dots ,c_k):c_1+c_2+\cdots +c_k=n+1,c_j\ge 1,c_k\ge 2}{1}^{c_1}{2}^{c_2}\cdots k^{c_k}+\sum _{(c_1,\dots ,c_k):c_1+c_2+\cdots +c_k=n+1,c_j\ge 1,c_k=1}{1}^{c_1}{2}^{c_2}\cdots k^{c_k}\\ & =\sum _{(c_1,\dots ,c_k):c_1+c_2+\cdots +c_k=n+1,c_j\ge 1}{1}^{c_1}{2}^{c_2}\cdots k^{c_k}.\end{array}$

Zur bewiesenen Aussage