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.
Best Answer
I'm a bit surprised that this exercise appears so early in a combinatorics book without any hints.
Regarding your first question, yes, I understand the question the same way. What I don't understand is how you originally expected us to help you in interpreting the question without linking to your book or explaining what the "first row" was. I'd suggest to always directly link to any book you're referring to if it's available online, and also not to change the spelling if you quote from a book – I searched for the problem before you provided the link and would have found it if you hadn't changed the spelling of "labeled" to "labelled" :-)
Regarding your second question: What you want to count isn't the ways of labelling the vertices of a given graph; you want to count all such graphs with all labellings for all structures; so I don't think this approach will get you very far.
The problem itself doesn't define what exactly a rooted trivalent tree is. In particular, it's not immediately clear whether the root itself can have degree $1$ or $3$ or only one of the two. Unfortunately Google Books doesn't show (at least to me) the page with Figure 14.3 that the problem refers to, which would probably resolve this. However, this page seems to indicate that the root may be required to have degree $1$, which would fit with how this book seems to be use the term, and also with this solution, which apparently makes that assumption.
The given condition is equivalent to the condition that the vertices are labelled in decreasing order as viewed from the root. Thus we're counting the number of labelled full/proper/strictly binary trees with vertex labels increasing from the root.
The recurrence
$$a_n=\frac12\sum_{k=1}^{n-1}\binom{2n-2}{2k-1}a_na_{n-k}$$
derived in the solution linked to yields the initial terms $1,1,4,34,496,\dotsc$, which lead to OEIS sequence A002105.