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|$.

Answer 2

The total number of functions are $5^{10}$. Of these, the number of functions that do not take the value $1$, $2$, $3$, $4$ or $5$ are $4^{10}$. The number of functions that do not take the value $1$ and $2$, $3$ and $4$ and so on are $3^{10}$. Extending this argument, we get the number of surjective functions $$S=5^{10}-{5\choose{1}}4^{10}+{5\choose{2}}3^{10}-{5\choose{3}}2^{10}+{5\choose{4}}1^{10}=5103000.$$