# Number of idempotent functions

I'm supposed to show that the number of functions $$\ \mathrm{f}$$: $$[n]$$ $$\to$$ $$[n]$$ $$\$$ such that $$\mathrm{f\circ f=f}$$ is $$1+\sum _{k=1}^{n}{n \choose k}k^{n-k}$$

But I guess that this result only holds for $$\mathrm{n=0}$$ and that for $$\mathrm{n \ge 1}$$, the number of such functions is $$\sum _{k=1}^{n}{n \choose k}k^{n-k}$$. Is that so?

• For $f\circ f$ to equal $f$, there will be some number of fixed points. Specifically, suppose $a=f(x)$ for some $x$. Then $f(a)=a$ and $a$ is a fixed point. Pick which points are fixed points, and then for each point which is not a fixed point, pick which fixed point it maps to noting that whatever it maps to must be a fixed point as well. As for the added $1$ at the start, I agree, this should not be there. Oct 19, 2023 at 20:53
• Your formula is right: the case $n = 0$ is an exception and it is purely accidental that the incorrect formula you were given happens to work in that case. Oct 19, 2023 at 20:55
• ... that said, if you want a uniform formula that includes the case $n = 0$, then you can take the sum from $k = 0$ to $n$, as, following the usual conventions for $0^n$, the term for $k = 0$ will be $1$ when $n = 0$ and $0$ for positive $n$ Oct 19, 2023 at 21:09
• You can, of course, write the correct formula as $$\sum_{k=0}^n\binom nk k^{n-k},$$ which works for all $n\geq 0,$ because $0^0=1.$ Oct 19, 2023 at 22:24

You are correct, the formula $$1+\sum _{k=1}^{n}{n \choose k}k^{n-k}$$ is only equal to the number of $$f:[n]\to [n]$$ for which $$f\circ f =f$$ in the case $$n=0$$. For all $$n>0$$, you need to drop the "$$1+$$" out front to make the formula correct.
You can reformulate the problem statement as follows. I am using the convention that $$0^0=1$$.
For all $$n\ge 0$$, the number of functions $$f:[n]\to [n]$$ such that $$f\circ f=f$$ is $$\sum_{k=\color{red}0}^n \binom nk k^{n-k}$$
Proof: You can show that $$f\circ f=f$$ if and only if, for all $$y\in \text{im }f$$, that $$f(y)=y$$. To this end, for each subset $$K\subseteq [n]$$, let us count the number of $$f:[n]\to [n]$$ with the property that $$\text{im }f=K$$. For all $$y\in K$$, we must have $$f(y)=y$$, and for all $$z\notin K$$, we must have $$f(z)\in K$$. These are the only constraints, so the number of ways to choose $$f$$ is $$|K|^{n-|K|}$$.
Finally, we take the sum of $$|K|^{n-|K|}$$ over all $$K\subseteq [n]$$ to get the total number of functions. For each $$k\in \{0,1,\dots,n\}$$, there are $$\binom nk$$ subsets with cardinality $$k$$, and each of these contributes $$k^{n-k}$$ functions. Summing over all $$k$$ between $$0$$ and $$n$$, we arrive at the desired answer. $$\tag*{\square}$$
The entire reason this proof does not require casework depending on $$n=0$$ versus $$n>0$$ is because of the convention $$0^0=1$$. This is what allows to say that, for all sets $$A,B$$ with cardinalities $$|A|=a$$ and $$|B|=b$$, that the number of functions $$g:A\to B$$ is $$b^a$$, even in the edge cases where $$a=0$$ or $$b=0$$.