[Math] Counting Surjections with Inclusion-Exclusion

Question

Compute the number of surjective functions $f : [10] → [5]$ using the I/E principle.

With Stirling numbers of the second kind, we can obtain the answer with the following way $S(10,5)5!$. How I can get the answer with I/E principle?

Answer 1

For $1 \leq i \leq n$, let $A_i$ be the set containing all functions that do not map to element $i$ in the codomain.

For example, functions in $A_1$ can map to any element except $1$, so there are $4^{10}$ such functions. Functions in $A_1 \cap A_2$ can map to any elements except $1$ and $2$, so there are $3^{10}$ such functions.

Based on these examples, we have $|A_1 \cap \dots \cap A_j| = (5 - j)^{10}$, which can be subsituted into the inclusion-exclusion principle to enumerate all non-surjective functions. The total number of surjective functions will therefore be given by $5^{10} - |A_1 \cup \dots \cup A_5|$.