For all parts of this problem, let S be a finite set, with |S|=n. (a) If f:S -> S is onto, does it necessarily follow that f is invertible? Why or why not? (b) Compute the number of distinct functions g:S -> S that are onto. (c) Find the number of functions f:S -> S that are not invertible.
The Answer to the Question
is below this banner.
Here's the Solution to this Question
Let be a finite set with .
(a) If is onto and is finite, then is injection. Indeed, suppose that is not injection, then for some . It follows that , and therefore . This contadicts to the fact that is onto. Consequently, is bijection, and thus it is invertible.
(b) The number of distinct functions that are onto is equal to the number of all distinct bijection on the set . Taking into account that the number of all bijection on the set is equal to the number of all permutation of the -element set , we conclude that the number of distinct functions that are onto is equal to
(c) Let us compute the number of all functions . For each the value of the function at a point can independently acquire one of the values of the set . So, by the combinatorial rule of product, the number of all functions is equal to .
Consequently, the number of functions that are not invertible is equal to .