Diskrete Mathematik/Gemischte Satzabfrage/25/Aufgabe/Lösung

Es sei $R$ ein kommutativer Halbring und seien $x_{1}, \dots, x_{k} \in R$ Elemente und $n \in ℕ$ . Dann ist
${(x_{1} + \dots + x_{k})}^{n} = \sum_{r_{1} + \dots + r_{k} = n} (\binom{n}{r_{1}, \dots, r_{k}}) x_{1}^{r_{1}} \dots x_{k}^{r_{k}} .$
Es sei $A$ eine $n$ -elementige Menge und $B$ eine $k$ -elementige Menge. Dann ist die Anzahl der surjektiven Abbildungen von $A$ nach $B$ gleich
$\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}} .$
Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens vier Farben.