Endliche Mengen/Surjektive Abbildungen/5 nach 3/Beispiel

Wir bestimmen die Anzahl der surjektiven Abbildungen der fünfelementigen Menge ${}\{a,b,c,d,e\}$ in die dreielementige Menge ${}\{1,2,3\}$ mit Hilfe von Fakt, Fakt und Fakt. Zur Bestimmung der Summe aus Fakt betrachten wir zuerst die Indexmenge. Die möglichen Indextupel sind ${}(1,1,3)$ und ${}(1,2,2)$, jeweils mit drei Permutationen. Deshalb ist die Summe gleich

${}{\begin{aligned}\sum _{(r_{1},r_{2},r_{3}):\,r_{1}+r_{2}+r_{3}=n,\,r_{j}\geq 1}{\binom {5}{r_{1},r_{2},r_{3}}}&=3\cdot {\binom {5}{3,1,1}}+3\cdot {\binom {5}{1,2,2}}\\&=3\cdot 20+3\cdot 30\\&=150.\end{aligned}}$

Zur Bestimmung der Summe in Fakt betrachten wir wieder die Indextupel, wobei ähnlich wie soeben bis auf Permutationen die Summen ${}5=1+1+3=1+2+2$ möglich sind. Die zugehörigen Summanden hängen aber von den Permutationen ab. Es ist

${}{\begin{aligned}\sum _{(a_{1},a_{2},a_{3}):\,a_{1}+a_{2}+a_{3}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}3^{a_{3}}&=1^{1}\cdot 2^{1}\cdot 3^{3}+1^{1}\cdot 2^{3}\cdot 3^{1}+1^{3}\cdot 2^{1}\cdot 3^{1}+1^{1}\cdot 2^{2}\cdot 3^{2}+1^{2}\cdot 2^{1}\cdot 3^{2}+1^{2}\cdot 2^{2}\cdot 3^{1}\\&=54+24+6+36+18+12\\&=150.\end{aligned}}$

Die Summe aus Fakt ist

${}\sum _{j=0}^{3}(-1)^{3-j}{\binom {3}{j}}j^{5}=-1\cdot 0^{5}+3\cdot 1^{5}-3\cdot 2^{5}+3^{5}=3-96+243=150\,.$