How many functions can be constructed? How many functions $f:\left\{1, 2, 3, 4,5 \right\} \rightarrow \left\{ 1, 2, 3, 4, 5 \right\}$ satisfy the relation $f\left( x \right) =f\left( f\left( x \right)  \right)$ for every $x\in \left\{ 1, 2, 3, 4, 5 \right\}$?
My book says the answer is 196.
 A: Hint:  Let $R\subset\{1,2,3,4,5\}$ be the range of $f$.
Then $f(x)$ is completely determined  for every $x\in R$, and the only choices you have about the behavior of $f$ are for $x\notin R$.
Hint 2: If $\{1,2,3,4,5\}$ is too complicated, try solving the problem for $\{1,2\}$ instead, and then see if you can apply the same method to the $\{1,2,3,4,5\}$ case.
Hint 3:  Suppose that $R$ has exactly $n$ elements, and then try to count the number of functions $f$ satisfying $f(f(x))=f(x)$.
A: Let $D$ be the domain of $f$, $\{1,2,3,4,5\}$, and let $R\subset D$ be the range of $f$.  We want $f(f(x)) = f(x)$ for all $x$, and since $f(x) = y$ if and only if $y\in R$, we have $f(y) = y$ if and only if $y\in R$.
Suppose $|R| = n$.   There are $\binom 5n$ ways to pick $R$ itself. For each of these,  $f(x)$ is completely determined when $x\in R$ (it is $x$) and when $x\notin R$, we have $n$ choices for $f(x)$.  There are $5-n$ elements of $D\setminus R$, so $n^{5-n}$ choices for $f$, for each possible choice of $R$.  
For example, suppose $|R| = 2$.  There are $\binom52$ choices for $R$.  For each of the three elements $x\in D\setminus R$, there are 2 choices for $f(x)$, for a total of $2^3=8$ functions for each choice of $R$.  So there are $\binom52\cdot 8 = 80$ functions which have $|R|=2$.
The total number of functions $f$ is then $$\begin{align}
\sum_{n=1}^5 \binom5{n}n^{5-n} & =
   \binom51\cdot 1^4 + \color{maroon}{\binom52\cdot 2^3} + \binom 53\cdot 3^2 + \binom 54\cdot 4^1 + \binom 55\cdot 5^0 \\
  &= 5 \cdot 1 + \color{maroon}{10\cdot8} + 10\cdot 9+5\cdot4+ 1\cdot1 \\&= 196
\end{align}$$ where the colored term is the example from the previous paragraph.
