csat-suneung 2019 Q17
4 marks
Counting Functions or Mappings with Constraints
The following is a process to find the number of functions $f$ such that the number of elements in the range of the composite function $f \circ f$ is 5, for the set $X = \{ 1,2,3,4,5,6 \}$ and the function $f : X \rightarrow X$.
Let the ranges of the function $f$ and the function $f \circ f$ be $A$ and $B$, respectively. If $n ( A ) = 6$, then $f$ is a bijection, and $f \circ f$ is also a bijection, so $n ( B ) = 6$. Also, if $n ( A ) \leq 4$, then $B \subset A$, so $n ( B ) \leq 4$. Therefore, we only need to consider the case where $n ( A ) = 5$, that is, $B = A$.
(i) The number of ways to choose a subset $A$ of $X$ with $n ( A ) = 5$ is (가).
(ii) For the set $A$ chosen in (i), let $k$ be the element of $X$ that does not belong to $A$. Since $n ( A ) = 5$, the number of ways to choose $f ( k )$ from the set $A$ is (나).
(iii) For $A = \left\{ a _ { 1 } , a _ { 2 } , a _ { 3 } , a _ { 4 } , a _ { 5 } \right\}$ chosen in (i) and $f ( k )$ chosen in (ii), since $f ( k ) \in A$ and $A = B$, we have $A = \left\{ f \left( a _ { 1 } \right) , f \left( a _ { 2 } \right) , f \left( a _ { 3 } \right) , f \left( a _ { 4 } \right) , f \left( a _ { 5 } \right) \right\} \cdots ( * )$. The number of cases satisfying (*) is equal to the number of bijections from set $A$ to set $A$, so $\square$ (다).
Therefore, by (i), (ii), and (iii), the number of functions $f$ we seek is $\square$ (가) $\times$ $\square$ (나) $\times$ $\square$ (다).
When the numbers that fit (가), (나), and (다) are $p , q , r$ respectively, what is the value of $p + q + r$? [4 points]
(1) 131
(2) 136
(3) 141
(4) 146
(5) 151