Endliche Mengen/Surjektive Abbildungen/Potenzprodukte/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$ (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 \geq k$ bewiesen. Unter Verwendung der Induktionsvoraussetzung und der Rekursionsformel ist die Anzahl der surjektiven Abbildungen von ${1, \dots, n + 1}$ nach ${1, \dots, k}$ gleich

\begin{matrix} = k \cdot \sum_{(a_{1}, \dots, a_{k}) : a_{1} + a_{2} + \dots + a_{k} = n, a_{j} \geq 1} 1^{a_{1}} 2^{a_{2}} \dots k^{a_{k}} \\ = \sum_{(a_{1}, \dots, a_{k}) : a_{1} + a_{2} + \dots + a_{k - 1} + a_{k} + 1 = n + 1, a_{j} \geq 1} 1^{a_{1}} 2^{a_{2}} \dots k^{a_{k} + 1} + k \cdot \sum_{(b_{1}, \dots, b_{k - 1}) : b_{1} + b_{2} + \dots + b_{k - 1} = n, b_{j} \geq 1} 1^{b_{1}} 2^{b_{2}} \dots (k - 1)^{b_{k - 1}} \\ = \sum_{(c_{1}, \dots, c_{k}) : c_{1} + c_{2} + \dots + c_{k} = n + 1, c_{j} \geq 1, c_{k} \geq 2} 1^{c_{1}} 2^{c_{2}} \dots k^{c_{k}} + \sum_{(b_{1}, \dots, b_{k - 1}) : b_{1} + b_{2} + \dots + b_{k - 1} + 1 = n + 1, b_{j} \geq 1} 1^{b_{1}} 2^{b_{2}} \dots (k - 1)^{b_{k - 1}} \cdot k^{1} \\ = \sum_{(c_{1}, \dots, c_{k}) : c_{1} + c_{2} + \dots + c_{k} = n + 1, c_{j} \geq 1} 1^{c_{1}} 2^{c_{2}} \dots k^{c_{k}} + \sum_{(c_{1}, \dots, c_{k}) : c_{1} + c_{2} + \dots + c_{k} = n + 1, c_{j} \geq 1, c_{k} = 1} 1^{c_{1}} 2^{c_{2}} \dots k^{c_{k}} . \end{matrix}

Zur bewiesenen Aussage