Question

Find the number of all onto functions from the set $\left\{ 1,2,3,...,n \right\}$ to itself.

Answer 1

Hint: A function from the set $\left\{ 1,2,3,...,n \right\}$ to itself is said to be onto if each of the elements from this set has a unique pre-image. Now start from small n, like 2 or 3. Find out the total number of onto mapping. Then try to generalize the result.

Complete step-by-step solution -
A function is said to be onto if every point from the co-domain set has a unique pre-image in the domain set.
Here the domain and the co-domain are the same. So we need to count those functions in which every point from the set $\left\{ 1,2,3,...,n \right\}$ has a unique pre-image.
Let us start with a small n.
For n = 3, the function is:
$f:\left\{ 1,2,3 \right\}\to \left\{ 1,2,3 \right\}$
If we start with point 1, the pre-images can be either 1 or 2 or 3.
After mapping 1, the next point 2 will get 2 choices. Like, if we map 1 to 1, then 2 can be mapped either into 2 or into 3.
After mapping 1 and 2, the last point 3 will get only one choice. Like, if we map 1 to 1, 2 to 3, then we have to map 3 to 2. Otherwise it will not be onto mapping.
Therefore, if we make a chart of elements and their possible number of pairings it will look like this:

Elements	Number of possible pairing
1	3
2	2
3	1

Similarly, if the set has n elements, we can map the first element to any one of the n elements. We can map the next element to any one of the (n-1) elements and so on.
Therefore,

Elements	Number of possible pairing
1	n
2	n-1
3	n-2
...	...
n-2	3
n-1	2
n	1

The total number of onto mappings will be:
$n\times \left( n-1 \right)\times \left( n-2 \right)\times ...\times 3\times 2\times 1$
$=n!$
Hence, the total number of onto functions from the set $\left\{ 1,2,3,...,n \right\}$ to itself is $n!$.

Note: Alternatively we can solve this problem by using mathematical induction. First we will show that for n = 1, the number of onto mapping is 1. For n = 2, the number of onto mappings are 2!, for n = 3 the number of onto mappings are 6, that is 3!. Then we will assume that for n = k, the number of onto mappings are k!. After that we will show that the statement is also true for n = k+1.