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.
 A: Not sure about correctness of this answer: if someone else could please proof-read...
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.
A: 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.
