# Number of functions with some property

A function $f$ is defined on the set $\{0,1,2,3,…,n-1\}$ to itself. This is a function such that if you take any $k$ from the set $\{0,1,2,3,…,n-1\}$ then $f^m (k)=0$ for some natural number $m$.

Question is how many such $f$ exist?

My strong conviction about the answer is $n^{n-1}$.

If it is, how can we prove this. I need the proof.

• If there a $m$ for all $k$ or a $m$ for each $k$? Jan 29, 2014 at 6:15
• m depends on k for sure. Jan 29, 2014 at 6:17

We want $f$ such that if you apply $f$ repeatedly, then you will arrive at $0$. This means that we must have some $f$ with no 'cycles', i.e. an $f$ s.t. $f(2) = 3$ and $f(3) = 2$ will be inadmissible because there is an input $k$ for $f$ s.t. $f^m(k) \neq 0$ for any $m \in \mathbb{N}$.

So let $V = \{0,1,2,3,\ldots,n-1\}$ be nodes in a graph $G = (V,E)$. How many ways are there to create a connected, acyclic graph? That's the same as asking in how many ways we can construct a tree on $G$. Now, Cayley's formula states that the number of trees on $n$ vertices is $n^{n-2}$. Note that $|V| = n$. So there are $n^{n-2}$ functions. Then we need to include the possibility that every node may map to $0$, so we have $n^{n-2} \cdot n = n^{n-1}$ functions.

• Note that there are $n$ ways to map $0$, so the answer is $n^{n-1}$ as conjectured and that "no cycles" means that any cycle contains $0$.
– benh
Jan 29, 2014 at 5:44
• What do you mean with that?
– Newb
Jan 29, 2014 at 5:45
• You associated the function $f$ with its corresponding functional graph. Now this graph will never be a tree (as there are as many edges as nodes). However, if you delete the out-edge of the node associated with $0$ you get a spanning tree of the graph. So in reverse you have to add an out-edge of $0$ to the acyclic graph to get the number of functions on $\{0, \dots , n\}$ with the desired property.
– benh
Jan 29, 2014 at 5:48

Draw a graph of the kind of function you want. That is: draw vertices labelled $0,1,\ldots,n-1$, and draw an arrow from $i$ to $j$ if $f(i)=j$. For the present draw no arrow coming out of $0$.

This graph cannot have a loop on a vertex $k$ other than $0$, as this would mean that $f(k)=k$ and so for all $m$ we have $f^m(k)=k\ne0$. Also, there are no cycles excluding $0$: for example, if $f(k)=l$ and $f(l)=k$ then $f^m(k)$ is always either $k$ or $l$ and is never $0$. And you can't have, say, a $3$-cycle with $f(k)=l$, $f(l)=m$, $f(k)=m$ as then $f$ would not be a well-defined function.

As $f^m(k)$ must always eventually be $0$ all the arrows must point towards $0$ and we can in fact ignore the directions, leaving a labelled tree. The number of labelled trees on $n$ vertices is known to be $n^{n-2}$.

Finally, add an arrow from $0$. It can go anywhere (including $0$ itself), so there are $n$ possibilities. Therefore the total number of graphs, and the total number of functions of this type, is $n^{n-1}$ as you conjectured.

• Yes David, I like the smart proof. Also I would like to thank Newb and Benh as well for initiation of the proof. Jan 29, 2014 at 5:54