The number of $f \circ f=f $

Question

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!

Answer 1

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}.$$

Answer 2

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.