Answer to Question #148093 in Discrete Mathematics for Promise Omiponle

Question

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.

Answer 1

Let $S$ be a finite set with $|S|=n$.

(a) If $f:S \to S$ is onto and $S$ is finite, then $f$ is injection. Indeed, suppose that $f$ is not injection, then $f(a)=f(b)$ for some $a\ne b$. It follows that $|f(S)|\le n-1$, and therefore $f(S)\subsetneq S$. This contadicts to the fact that $f$ is onto. Consequently, $f:S \to S$ is bijection, and thus it is invertible.

(b) The number of distinct functions $g:S \to S$ that are onto is equal to the number of all distinct bijection on the set $S$. Taking into account that the number of all bijection on the set $S$ is equal to the number of all permutation of the $n$-element set $S$, we conclude that the number of distinct functions $g:S \to S$ that are onto is equal to $n!.$

(c) Let us compute the number of all functions $f:S \to S$. For each $a\in S$ the value $f(a)$ of the function $f$ at a point $a$ can independently acquire one of the $n=|S|$ values of the set $S$. So, by the combinatorial rule of product, the number of all functions $f:S \to S$ is equal to $\underbrace{n\cdot...\cdot n}_n=n^n$.

Consequently, the number of functions $f:S \to S$ that are not invertible is equal to $n^n-n!.$ .