I understand rooted trees but I encountered an exercice where I was asked to find corresponding functions for rooted trees. What exactly is the function? And how can it be obtained?
Example: a 2-rooted line tree with one root at the start and one root at the end.
Another example: here I'm given $f(m)=m$ for all $m=1,2,3,...,n$ and I'm asked to find the 2-rooted tree for the function.
I am not asking for direct answers, I just need to understand how can the graph be presented in a function and what it means. Thank you!
It is likely that the exercise is referring to Joyal's proof of Cayley's formula.
Cayley's formula states that there are $n^{n-2}$ labeled trees on $n$ vertices. Joyal's strategy is to count doubly-rooted trees: that is, labeled trees on $n$ vertices with a distinguished "start" and "finish" node, which may be the same. There are always $n^2$ ways to choose the start and finish node, so it is enough to show that there are $n^n$ doubly-rooted trees. This is done by finding a bijection between doubly-rooted trees and the $n^n$ functions from the set $[n] = \{1,2,\dots,n\}$ to itself.
The link above goes into more detail about the bijection, but the idea is this. Given a doubly rooted tree, we distinguish two parts:
To define a function $f$, we first deal with the vertices on the start-to-finish path. Suppose these vertices have labels $i_1 < i_2 < \dots < i_k$ and the path visits them in the order $\sigma(i_1), \sigma(i_2), \dots, \sigma(i_k)$ for some permutation $\sigma$ of $\{i_1, i_2, \dots, i_k\}$. (So $\sigma(i_1)$ is the start node, and $\sigma(i_k)$ is the finish node.)
Then we define $f(i_j) = \sigma(i_j)$ for each of these vertices. For all other vertices $i$, there is a unique choice of neighbor closer to the start-to-finish path, and we let $f(i)$ be the label of that neighbor.