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 \)