Problem: Let $S=\{1,2,3,4,5\}$. How many functions $f: S \rightarrow S$ satisfy $f(f(x))=$ $f(x)$ for all $x \in S ?$ Solution: First, note that our $f$ need not satisfy $f(x) = x$ for all $x \in \{ 1,2,3,4,5 \}$ by any means as $x \mapsto 1$ is a perfectly valid mapping under this constraint. Now we ask, when is $f(f(x)) \neq f(x)$? This occurs when $f$ maps $f(x)$ to something other than $f(x)$. Effectively, we deduce that after a first application of $f$, all elements must be mapped to a fixed point. In other words, we must have $x$ map to some $y \in \{ 1,2,3,4,5 \}$ such that $f(y) = y$, otherwise the condition fails. Combinatorially, it suffices to count all ways we can assign fixed points (there must exist at least 1) and then assign the rest of the elements to those fixed points under $f$. Say we have $k$ fixed points in $f$ for some $1 \leq k \leq 5$. Then, there are $\binom{5}{k}$ ways to choose the fixed points from among the set $\{ 1,2,3,4,5 \}$ and then $k^{5-k}$ ways to map the non-fixed points *to* a fixed point. Hence, the answer is $\sum_{k = 1}^5 \binom{5}{k}k^{5-k} = 196$.