Math GRE - #2

If $S$ is a non-empty finite set with $k$ elements, then the number of one-to-one functions from $S$ onto $S$ is:

• $k!$
• $k^2$
• $k^k$
• $2^k$
• $2^{k+1}$

The answer is $k!$. Suppose our set only consisted of {1,2,3}. A function can be defined as a set of tuples that maps each element of the set to another element in the set (since we're looking at functions from $S$ to $S$). E.g. $f$ could be the function {(1,2), (2,3), (3,1)}. The left element in the tuple is an input to the function, the right element is an output. Note that we will always have three tuples in our function set, with the left element in each tuple being 1, 2, and 3 respectively.

So the question is: how many unique functions can we create by changing the numbers in the tuples? Well, we know the function is one to one, so we know that if our function was {(1, x), (2, y), (3, z)}, x, y, and z have to be different. If we take our example function and choose in the order x, y, z, there are 3 choices for x (out of {1, 2, 3}), 2 choices for y (out of {1, 3}) and only one choice for z (only {1} is left). So the total number of possible functions we could have had is: $3!=3\cdot2\cdot1=6.$ Thus, for a non-empty finite set with $k$ elements, then the number of one-to-one functions from $S$ onto $S$ is $k!$.

What if we didn't require the functions to be one-to-one? Which of the answers would it be?