How many surjective functions are there from $A=${$1,2,3,4,5$} to $B=${$1,2,3$}?

Solution 1:

I will show you two ways.

First one is with your current approach and using inclusion-exclusion, so you need to count the number of functions that miss at least $1$ element, lets call it $S_1$ which is equal to ${ 3 \choose 1 }2^5 = 96$. However, notice that this expression overcounts in the case of missing 2 elements. Everytime we count missing 1 and 3 for example, we also count missing 3 and 1 which are the same function. The number of functions that miss $2$ elements, call it $S_2$ is ${3 \choose 2}1^5 = 3$. Now, the total number of surjective functions is $3^5 - 96 + 3 = 150$.

But you can also do the following, fix a surjective function $f$ and consider the sets $f^{-1}(1), f^{-1}(2), f^{-1}(3)$. Because $f$ is surjective, they partition $A$ into $3$ disjoint, non empty sets.

Now think the other way around, start with $A$ and partition it into $3$ disjoint non empty sets, say $A_1, A_2, A_3$, you can then form a surjective function by just assigning one of the $A_i$ to one of the elements in $B$. The number of ways to partition a set of $n$ elements into $k$ disjoint nonempty sets are the Stirling numbers of the second kind, and the number of ways of of assigning the $A_i$ to the elements of $B$ is $k!$ (where $k$ is the size of $B$), in your particular case, this gives $3!S(5,3) = 150$.

The reason I showed you these two ways, is that you can use them to prove the "explicit" formula for the stirling numbers of the second kind, which is $$ k!S(n,k) = \sum_{j=0}^k (-1)^{k-j}{k \choose j} j^n $$ By just double counting, and using a more general inclusion exclusion, and as far as I know, this is one of the most "explicit" formulas you can get.