Problem:
Find the number of functions $f(x)$ from $\{1, 2, 3, 4, 5\}$ to $\{1, 2, 3, 4, 5\}$ that satisfy $f(f(x)) = f(f(f(x)))$ for all $x$ in $\{1, 2, 3, 4, 5\}$.
Solution:
Note that there are $5^5$ possible functions $f(x)$.
Now consider the probability of picking a function from those $3125$ functions that satisfies, exclusively, one of the following criteria:
$P(x = f(x) = f(f(x)) = f(f(f(x)))) = \frac{1}{5^5}$
$P(x \neq{f(x)} = f(f(x)) = f(f(f(x)))) = \frac{1}{5^4}$
$P(x = f(x) \neq{f(f(x))} = f(f(f(x)))) = \frac{1}{5^2}$
$P(x \neq{f(x)} \neq{f(f(x))} = f(f(f(x)))) = \frac{1}{5}$
Thus the number of functions $f(x)$ satisfying the condition stated in the problem is given by:
$\frac{5^5}{5^5} + \frac{5^5}{5^4} + \frac{5^5}{5^2} + \frac{5^5}{5} = 1 + 5 + 125 + 625 = \boxed{756}$.
Let $S = \{1,2,3,4,5\}$. We are told that $f(x)=x$ on $f^2(S) = \{f(f(s)): s \in S\}$. On the other hand, if $f(x)=x$ then $x = f(f(x)) \in f^2(S)$. Now $f^2(S) \subseteq f(S) \subseteq S$. If $f(S) = S$, then $f^2(S) = S$ as well, and $f(x)=x$ for all $x$. If not, $f$ maps $S \backslash f(S)$ into $f(S)$, and maps $f(S) \backslash f(f(S))$ into $f(f(S))$. Each point of $f(S) \backslash f(f(S))$ is the image of a point of $S \backslash f(S)$. There are the following possibilities for cardinalities of $S \backslash f(S)$, $f(S) \backslash f(f(S))$, and $f(f(S))$:
$0,0,5$
$1,0,4$
$1,1,3$
$2,0,3$
You can then compute the number of possibilities in each case. For example, for the case $2,2,1$, there are $5!/(2!2!1!)= 30$ ways to choose which points go in which set, then $2$ ways to map the two points of $S \backslash f(S)$ to $f(S) \backslash f(f(S))$, and only one way to do the rest (both points of $f(S) \backslash S$ must map to the one point of $f(f(S))$, and that point maps to itself), so $30 \times 2 = 60$ functions corresponding to this case.