Paragraph

1. There are \(4^5\) functions all together; we will subtract the functions which are not surjective. We could exclude any one of the four elements of the codomain, and doing so will leave us with \(3^5\) functions for each excluded element. This counts too many so we subtract the functions which exclude two of the four elements of the codomain, each pair giving \(2^5\) functions. But this excludes too many, so we add back in the functions which exclude three of the four elements of the codomain, each triple giving \(1^5\) function. There are \({4 \choose 1}\) groups of functions excluding a single element, \({4 \choose 2}\) groups of functions excluding a pair of elements, and \({4 \choose 3}\) groups of functions excluding a triple of elements. This means that the number of functions which are not surjective is:

   \begin{equation*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\text{.} \end{equation*}

   We can now say that the number of functions which are surjective is:

   \begin{equation*} 4^5 - \left[{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right]\text{.} \end{equation*}

2. The number of surjective functions is:

   \begin{equation*} 5^5 - \left[{5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right]\text{.} \end{equation*}

   We took the total number of functions \(5^5\) and subtracted all that were not surjective. There were \({5 \choose 1}\) ways to select a single element from the codomain to exclude from the range, and for each there were \(4^5\) functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are \({5 \choose 2}\) choices for the two elements to exclude, and for each pair, \(3^5\) functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: \({5 \choose 3}\) choices for which three to exclude, and then \(2^5\) functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the \({5 \choose 4}\) choices of 4 elements.

   If you happen to calculate this number precisely, you will get 120 surjections. That happens to also be the value of \(5!\text{.}\) This might seem like an amazing coincidence until you realize that every surjective function \(f:X \to Y\) with \(\card{X} = \card{Y}\) finite must necessarily be a bijection. The number of bijections is always \(\card{X}!\) in this case. What we have here is a combinatorial proof of the following identity:

   \begin{equation*} n^n - \left[{n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right] = n!\text{.} \end{equation*}