I am trying to solve the following problem in my book: (Code stands for Prüfer code)
Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are chosen in such a way that the procedure leading to $P(T)$ has $1,2,\cdots 2n-1$ as first row. How many possible codes $P(T)$ are there?
As I understand the question, it is asking for the number of ways of labeling the tree such that if we run the Prüfer algorithm, first time the vertex labeled $1$ is removed, second time the vertex labeled $2$ is removed and so on, until the vertex labelled $2n-1$ is removed. Is my understanding of the question correct?
There are going to be $n+1$ monovalent vertices in such trees, which means there are $n+1$ ways to label a vertex as $1$. But how many ways will be there to label a vertex as $2$? As soon as a vertex has been labeled as $1$, and removed in the first iteration there are either $n$ monovalent vertices remaining or $n+1$ monovalent vertices remaining. So there seem to be two possibilities for labeling $2$: either among $n$ or among $n+1$. How do I decide the number of ways of choosing $2$.
An example of such a rooted trivalent tree is:
Thanks.