# Number of possible Prüfer codes

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?

1. 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?

2. 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$.

3. An example of such a rooted trivalent tree is:

Thanks.

-
Presumably $P(T)$ refers to the Prüfer code for $T$? What does "as first row" refer to? In the Prüfer code as described e.g. in the Wikipedia article you link to, there are no rows. (Note that you misspelled the name of the code; if you don't have umlauts on your keyboard, you can copy them e.g. from the Wikipedia article.) – joriki Feb 8 '12 at 8:13
Yes $P(T)$ means Prüfer code. By the first row we mean the finite sequence of monovalent vertices of smallest label which we remove to get a smaller tree. (I have linked the description of the Prüfer codes in my book instead of the wikipedia link now.) – Shahab Feb 8 '12 at 8:29
Thanks. Google Books won't let me see that page; here's a link that works for me. – joriki Feb 8 '12 at 8:51
Since you've put up a bounty for this, perhaps you should explain what you'd like to see in addition to my answer? – joriki Feb 10 '12 at 16:34
Oh I don't mean to say that your explanation is insufficient. I would just like to make sure that our understanding of the question is correct by getting some other opinions. – Shahab Feb 11 '12 at 2:18

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.

-
Thank you for taking the time out to answer me. I am really grateful. I have uploaded a figure which appeared as an example in the book for a rooted trivalent tree, and which confirm your conjecture of the root being of degree 1. However recurrence relations appear later down in the book so I don't think its expected that they are to be used in the solution. – Shahab Feb 8 '12 at 15:48
@Shahab: You're welcome. I agree that this doesn't seem like the right sort of solution at this point in the book, but as you can see on the page I linked to, the explicit solution for the recurrence relation is a rather complicated expression involving several powers and Bernoulli numbers, so it also seems unlikely that this could be derived by more suitable means. It could be that a) this was meant as an advanced exercise, b) there's something wrong with the solution, c) we're misunderstanding the question or d) the authors got the solution wrong and erroneously thought it was easy. – joriki Feb 8 '12 at 16:16