2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If there a $m$ for all $k$ or a $m$ for each $k$? $\endgroup$
    – Neil W
    Jan 29, 2014 at 6:15
  • $\begingroup$ m depends on k for sure. $\endgroup$
    – Fukuzita
    Jan 29, 2014 at 6:17

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – benh
    Jan 29, 2014 at 5:44
  • $\begingroup$ What do you mean with that? $\endgroup$
    – Newb
    Jan 29, 2014 at 5:45
  • $\begingroup$ 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. $\endgroup$
    – benh
    Jan 29, 2014 at 5:48
0
$\begingroup$

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.

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

You must log in to answer this question.

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