2
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Oct 19, 2023 at 20:53
  • $\begingroup$ 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. $\endgroup$
    – Rob Arthan
    Oct 19, 2023 at 20:55
  • 1
    $\begingroup$ ... 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$ $\endgroup$
    – Rob Arthan
    Oct 19, 2023 at 21:09
  • $\begingroup$ 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.$ $\endgroup$ Oct 19, 2023 at 22:24

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .