Number of functions verifying $f(f(x))=f(x)$. Find the number of functions $f:\{1,2,3,4\}\to \{1,2,3,4\}$ that verify $f(f(x))=f(x)$. I'm not sure if the answer is $41$ or $29$.
 A: A function satisfying $f(f(x))=f(x)$ is called idempotent, and such functions, as Marc said in a comment, are the identity on their image (i.e., if $y\in\operatorname{im} f$ then $f(y)=y$).
Every subset of $\{1,2,3,4\}$ is possible as an image of $f$ (and there are $2^4=16$ of these), so we must count the number of possible ways of obtaining such images.  If the image is a one-element set, then there are four options, the four constant functions.  If the image is a two-element set, then there are two elements which aren't fixed and there are four possible options for them.  If the image is a three-element set, then the fourth element has three possible images, and if the image is a four-element set, then the identity function is the only option.  Thus, the number is
$$4 + 4\binom{4}{2} + 3\binom{4}{3} + 1=41.$$
In fact, we can generalize this to $\sum_{i=1}^ni^{n-i}\binom{n}{i}$ for a function $f:\{1,\dots,n\}\to\{1,\dots,n\}$.  There are $\binom{n}{i}$ subsets of an $n$-element set, and for each set the remaining $n-i$ elements can map to any of the $i$ fixed elements in that set.
A: I'll try to enumerate them based on the number of fixed points.
If you have $4$ fixed points, $f$ is the identity. So there's only one possibility.
If you have $3$, the one left can't be mapped to itself. So we have ${4\choose 3}\cdot 3$ possibilities.
If you have $2$, we'll call the ones left $i,j$. If $f(i)=j$ then $f(j)=f(f(i))=f(i)=j$, which is wrong since $j$ isn't a fixed point. So they're both mapped to the fixed points. ${4\choose 2}\cdot2\cdot2$ possibilities.
If you have one fixed point. By the same reasoning, all of the others map to it. ${4\choose 1}$ possibilities.
The final result is: $1+12+24+4=41$
A: Since $f$ maps it's image to itself, any number in the image must come from itself. Now count:
There is only a single number in $f(x)$. This gives four options: $1111, 2222 ...$
Only two numbers in the output. Two numbers are determined, and the rest can be anything. Thus we have another:
$${4 \choose 2} \cdot 2^2 = 24$$
Options.
If there are three numbers in the output we have:
$${4\choose 3}\cdot 3 = 12$$
More options. Add the identity map to these to get:
$$41$$
