Indian Statistical Institute B.Math & B.Stat : Combinatorics

Let $A = \{1,2,3,4,5,6\}$. Find the number of functions $f$ from $A$ to $A$ such that range of $f$ contains exactly $5$ elements. $5$ elements of the range can be selected in $\binom {6}{5} = 6$ ways. Now we will find the number of onto functions (since the range of $f$ contains exactly $5$ elements) for each such case. Thus the problem reduces to finding the number of onto functions from a set containing $6$ elements to a set containing $5$ ($\{ 2,3,4,5,6\} \quad say$) elements. Let $T_1$ be the set of all functions with the property that the element $2$ is not in the range of the function. Let $T_2$ be the set of all functions with the property that the element $3$ is not in the range of the function. $$\dots$$ Let $T_5$ be the set of all functions with the property that the element $6$ is not in the range of the function. Now the function will be onto ( i.e., the range of f will contain exactly $5$ elements ) $iff$ none of the above properties hold. Number of such functions is $|T_1 \cup T_2 \cup \dots \cup T_5|$. Using the principle of $Exclusion-Inclusion$ we have $|T_1 \cup T_2 \cup \dots \cup T_5| = \sum_{i=1}^{5} |T_i|- \sum_{1 \leq i < j < \leq 5}^{} |T_i \cap T_j| + \dots + |T_1 \cap T_2 \cap \dots \cap T_5|$ $= \binom{5}{1} 4^6 - \binom{5}{2} 3^6 + \binom{5}{3} 2^6 - \binom{5}{4} 1^6 + \binom{5}{5} 0^6 = 13825$ Total number of functions = $5^6 = 15625$ Therefore number of functions with required condition $= (15625 - 13825) \times \binom {6}{5} = 10800$