The number of $f \circ f=f $ Let $A=\{1,2,3...n\}$，How many functions satisfy the following conditions？
(1) $f \circ f=f $
(2) $f \circ f =I_A$
(3) $f \circ f\circ  f=I_A$
$\circ$ is composite.
The question is from a 'Discrete Mathematics' book, and the book gave the answer of the first two questions.
(1)  $n+1$
(2) $ C_n^2+1(\tbinom{n}{2}+1)$
But I think the answer of first is wrong.It should be $\sum_{k=0}^{n}{\tbinom{n}{k}k^{n-k}}$.
For the $f$ satisfied (1), The $f=\{<1,b_1>,<2,b_2>,...<n,b_n>\}$, and if $ b_n\neq n$, there is $<b_n,b_n>$ in $f$.
EDIT
For the answer I gave, I think it's wrong now.Because I think it contains repeated parts.That is, it is bigger than the correct answer.
I want to konw my answer whether is correct,and get the answer or hint of the three questions
Any help would be greatly appreciated :-)
Thanks very much!
 A: First of all, the answer in the book is obviously wrong for $n = 1$ as there is only $1$ possible map to begin with.
Now for the actual solution, assume that $f$ satisfies (1). Set $B := f(A)$. By assumption we must have $f(x) = x$ for all $x \in B$. For $x \notin B$, there is no further restriction, it can be mapped to any point in $B$. There are $n \choose k$ ways to choose the set $B$ with $k$ elements. For the remaining $n-k$ elements there are $k$ possible choices each. We would therefore come up with
$$\sum\limits_{k = 1}^n {n \choose k} k^{n-k}.$$
A: First observe that the number of $f$'s satisfying $(ii)$ is precisely the number of elements in $S_n$ (the symmetric group with $n$-symbols) of order $2$ and similarly the number of $f$'s satisfying $(iii)$ is precisely the number of elements in $S_n$ of order $3.$
Now an element in $S_n$ of order $2$ is of the form $(a_{11}\ a_{12}) (a_{21}\ a_{22}) \cdots (a_{k1}\ a_{k2})$ for some $1 \leq k \leq \left [ \frac n 2 \right ]$ and similarly an element in $S_n$ of order $3$ is of the form $(a_{11}\ a_{12}\ a_{13}) (a_{21}\ a_{22}\ a_{23}) \cdots (a_{k1}\ a_{k2}\ a_{k3})$ for some $1 \leq k \leq \left [ \frac n 3 \right ].$
Now the number of elements in $S_n$ of the form $(a_{11}\ a_{12}) (a_{21}\ a_{22}) \cdots (a_{k1}\ a_{k2})$ for some $1 \leq k \leq \left [ \frac n 2 \right ]$  is $\frac {\binom n 2 \binom {n-2} {2} \cdots \binom {n-2n+2} {2}} {k!}$ which simplifies to $\frac {n!} {2^k k! (n-2k)!}$ and similarly the number of elements in $S_n$ of the form $(a_{11}\ a_{12}\ a_{13}) (a_{21}\ a_{22}\ a_{13}) \cdots (a_{k1}\ a_{k2}\ a_{k3})$ for some $1 \leq k \leq \left [ \frac n 3 \right ]$  is $\frac {\binom n 3 \binom {n-3} {3} \cdots \binom {n-3n+3} {3}} {k!}$ which simplifies to $\frac {n!} {6^k k! (n-3k)!}.$
So the answer to $(2)$ is given by
$$\sum\limits_{k=1}^{\left [\frac n 2 \right]} \frac {n!} {2^k k! (n-2k)!}.$$
and similarly the answer to $(3)$ is given by
$$\sum\limits_{k=1}^{\left [\frac n 3 \right]} \frac {n!} {6^k k! (n-3k)!}.$$
But sorry I don't know any further simplification of the above summations.
