Number of idempotent endomorphisms of [1,n] The question asked was: let $A=\{1,2,...n\}$
how many functions $f:A\mapsto A$ such that $f$ is idempotent? That is, $f \circ f = f$
By considering the possible cardinal of the set of fixed points of such functions, I found that there are $\sum_{k=0}^{n}{{{n}\choose k}\times k^{n-k}}$ such functions. 
However, I couldn't find a simpler expression for this sum, either by looking for a recursion formula, or by computing it directly.
Do you have any idea how to simplify it? I have thought about finding another form by double counting the number of functions
 A: Let $S$ be the set of idempotent functions. It is convenient to write $S$ as the disjoint union of $S_i$, where 
$S_i$ is the subset of functions $f$ such that $|Im(f)|=i$. It is clear that 
$S=\bigcup_{i\in \{1,\dots ,n\}}S_i$ and $S_i\cap S_j=\emptyset$ if $i\neq j$.
So
$|S|=\sum_{i=1}^n|S_i|$
You can observe that if $f$ is idempotent then $Im(f)=Fix(f)$ because if $x\in Im(f)$ then $x=f(y)$ and so 
$f(x)=f\circ f (y)=f(y)=x$
Now we want to determine the cardinality of $S_i$ for each $i\in \{1,\dots, n\}$:
$|S_n|=1$, infact there is only a surjective function $f$ such that $f\circ f=f$. This function is $Id_A$ because $f$ is a bijective map and then
$f=f^{-1}\circ(f\circ f)=f^{-1}\circ f=Id_A$
Let $f\in S_{n-1}$, then $Im(f)$ has cardinality $n-1$. If we suppose that $n\not \in Im(f)$ then $Im(f)=\{1,\dots, n-1\}$, but each point of the image of $f$ is a fixed point, so $f$ fixes the first $n-1$ points, because $Im(f)=\{1,\dots , n-1\}$. Then the number of functions $f$ that have image  $\{1,\dots ,n-1\}$ is $n-1$. So we have 
$S_{n-1}=(n-1)*$(number of way to subtract a single point from a set of $n$ points)$=n(n-1)$
We must consider also the case $S_{n-2}$ to get an intuition of what happened. 
Let  be $f\in S_{n-2}$ and we suppose that 
$Im(f)=\{1,\dots n-2\}$
In this case that points are fixed points for $f$, so we have only 2 points that can be mapped by $f$ in $(n-2)^2$ different way. So we have 
$S_{n-2}=(n-2)^2*$(number of way to subtract $2$ points from a set of $n$ points)$=(n-2)^2\binom{n}{2}$
In general 
$S_{n-k}=(n-k)^k\binom{n}{k}$
So
$|S|=\sum_{k=0}^{n-1}|S_{n-k}|=\sum_{k=0}^{n-1}(n-k)^k\binom{n}{k}$
