1
$\begingroup$

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!

enter image description here

$\endgroup$
7
  • $\begingroup$ Can you say where you encountered the exercise and what the wording was? The words "corresponding function" are not standard mathematical terminology, so it's probably referring to some correspondence between rooted trees and functions defined earlier. $\endgroup$ Apr 27, 2019 at 22:31
  • 1
    $\begingroup$ You are missing context. What is a "2-rooted tree"? What is the definition of "corresponding function for rooted trees". I have never encountered a "2-rooted tree". $\endgroup$
    – Somos
    Apr 27, 2019 at 22:33
  • $\begingroup$ @MishaLavrov it was sent to us as a practice exercice for an examination. I was also confused with the wording that's why I asked the question to see if anyone has an idea since google failed me. $\endgroup$
    – bluemuse
    Apr 27, 2019 at 23:08
  • $\begingroup$ @Somos 2-rooted trees seem to mean trees with 2 roots, given the graphs that came with the exercice all had 2 roots $\endgroup$
    – bluemuse
    Apr 27, 2019 at 23:08
  • $\begingroup$ No definition came for the corresponding function. $\endgroup$
    – bluemuse
    Apr 27, 2019 at 23:09

1 Answer 1

1
$\begingroup$

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:

  • A path from the start node to the finish node.
  • All the other vertices.

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – bluemuse
    Apr 28, 2019 at 19:28

You must log in to answer this question.

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