Again start with the total number of functions:
(as each of the five elements of the domain can go to any of three elements of the codomain). Now we count the functions that are
not surjective.
Start by excluding
from the range. Then we have two choices (
or
) for where to send each of the five elements of the domain. Thus there are
functions that exclude
from the range. Similarly, there are
functions that exclude
and another
that exclude
Now have we counted all functions that are not surjective? Yes, but in fact, we have counted some multiple times. For example, the function which sends everything to
was one of the
functions we counted when we excluded
from the range, and also one of the
functions we counted when we excluded
from the range. We must subtract out all the functions which specifically exclude two elements from the range. There is 1 function when we exclude
and
(everything goes to
), one function when we exclude
and
and one function when we exclude
and
We are using PIE: To count the functions that are not surjective, we added up the functions that exclude and separately; then subtracted the functions that exclude pairs of elements. We would then add back in the functions that exclude groups of three elements, except that there are no such functions. We find that the number of functions that are not surjective is
Perhaps a more descriptive way to write this is
since each of the βs was the result of choosing 1 of the 3 elements of the codomain to exclude from the range; each of the three βs was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing instead of 1 makes sense too: We have 1 choice of where to send each of the 5 elements of the domain.
Now we can finally count the number of surjective functions: