Number of idempotent functions

56 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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