Prüfer-Code Counts For Constrained Labeled Trees

From Tree Conditions to Code Conditions

For a labeled tree, a degree condition is a condition on how often a label appears in its Prüfer sequence. A condition on a particular position in that sequence adds a different kind of restriction: it fixes a symbol in a specified place. Keeping these two translations distinct makes it possible to count trees subject to both kinds of condition.

Throughout, the labels form a fixed set $V$ of size $n\ge2$, and all trees are simple labeled trees on exactly $V$. A Prüfer sequence has length $L=n-2$, with entries in $V$. We use the standard Prüfer-code bijection: each such sequence corresponds to exactly one labeled tree, and a label $i$ occurs exactly $\deg(i)-1$ times in the sequence. These facts are established in the earlier material on Prüfer codes; the counting arguments below apply them directly.

Definition: For a label $i$, let $a_i$ be its required number of occurrences in the Prüfer sequence. If its degree is prescribed to be $d_i$, then $a_i=d_i-1$. A degree condition for a label is therefore equivalent to an occurrence-count condition for that label.

For example, if a tree on at least two vertices has a prescribed degree $1$ at label $i$, then $a_i=0$: the label must not appear in the code. If its degree is $3$, then it must appear exactly twice. This translation is the starting point for both degree counts and position constraints.

A Formula for Partial Degrees and Fixed Positions

It is useful to allow degree conditions on only some labels. Let $S\subseteq V$ be the set of labels whose degrees are prescribed, with prescribed positive integer degrees $d_i$ for $i\in S$. Write $a_i=d_i-1$. Separately, let $P\subseteq\{1,\ldots,L\}$ be a set of distinct code positions with a specified label $b_p\in V$ required at each position $p\in P$. A position condition is an equality: the entry at position $p$ must be exactly $b_p$.

For each constrained label $i\in S$, let $r_i$ be the number of prescribed positions whose specified entry is $i$. There are $M=L-|P|$ unprescribed positions. After accounting for the fixed entries, label $i$ still needs $c_i=a_i-r_i$ occurrences in those $M$ positions. Define

R=M-\sum_{i\in S}c_i,\qquad q=n-|S|.

Here $R$ is the number of unprescribed positions left for labels outside $S$, and $q$ is the number of labels outside $S$. A negative $c_i$, a negative $R$, or $R>0$ when $q=0$ makes the requirements impossible.

Theorem: Under the conditions above, the number of labeled trees satisfying all the degree and position requirements is zero if any $c_i<0$, if $R<0$, or if $q=0$ and $R>0$. Otherwise the number is $$ \frac{M!}{R!\prod_{i\in S}c_i!}\,q^R, $$ where $0^0$ is interpreted as $1$.

Proof. The Prüfer-code bijection reduces the tree count to the number of length-$L$ sequences satisfying the corresponding conditions. The $|P|$ fixed entries leave $M$ positions to fill. For each $i\in S$, exactly $c_i$ of those positions must contain $i$. If any $c_i<0$, the already fixed entries use more copies of $i$ than the degree requires, so there are no sequences. If $\sum_{i\in S}c_i>M$, then $R<0$, so there are not enough positions. In the remaining case, first choose which $c_i$ positions hold each constrained label $i$, and leave the remaining $R$ positions for labels outside $S$. The number of ways to make these position choices is $M!/(R!\prod_{i\in S}c_i!)$. Each of the $R$ remaining positions has $q$ possible labels, independently, giving $q^R$ fillings. If $q=0$, such a filling exists exactly when $R=0$, and then it has one possibility; this is the stated $0^0=1$ convention. Each resulting sequence is a distinct Prüfer code and therefore represents one tree, so the formula counts exactly the required trees. $\square$

If all labels have prescribed degrees and no positions are fixed, the formula has $q=0$. It gives zero unless the required occurrence counts add to the full sequence length; when they do, it gives the usual multinomial count. The formula also handles unconstrained degrees: any remaining positions can use any label outside $S$, with no additional degree restriction on those labels.

Worked Counts on Four and Five Labels

Worked Example: Partial Degree Conditions on Four Labels

Let $V=\{1,2,3,4\}$. Count the trees satisfying $\deg(1)=2$ and $\deg(2)=1$, with no degree condition on labels $3$ and $4$.

The code length is $L=4-2=2$. The conditions require $a_1=2-1=1$ occurrence of label $1$, and $a_2=1-1=0$ occurrences of label $2$. Here $S=\{1,2\}$, so $q=4-2=2$, and there are no fixed positions. Thus $M=2$, $c_1=1$, $c_2=0$, and $R=2-(1+0)=1$. The formula gives

\frac{2!}{1!\,1!\,0!}\,2^1=2\cdot2=4.

Check: the valid codes are $13,14,31,41$. Each has exactly one occurrence of $1$, no occurrence of $2$, and one remaining entry from $\{3,4\}$. Thus there are four codes, agreeing with the formula. By the Prüfer bijection, they give four trees.

Worked Example: A Required Entry on Five Labels

Let $V=\{1,2,3,4,5\}$. Count the trees with $\deg(1)=3$, $\deg(2)=2$, and entry $2$ in position $1$ of the code.

The code length is $L=5-2=3$. The degree conditions require $a_1=3-1=2$ copies of $1$ and $a_2=2-1=1$ copy of $2$. The fixed entry uses the only required copy of $2$. With $S=\{1,2\}$, there are $q=5-2=3$ labels outside $S$, $M=3-1=2$ positions left, $c_1=2$, $c_2=1-1=0$, and $R=2-(2+0)=0$. The count is

\frac{2!}{0!\,2!\,0!}\,3^0=1.

The unique code is $2,1,1$. Decoding it gives the edges $23,12,14,15$: first the smallest label absent from the code, $3$, is joined to $2$; then $2$ is joined to $1$; then $4$ is joined to $1$; and the final two labels $1,5$ are joined. The degrees are $\deg(1)=3$, $\deg(2)=2$, and $\deg(3)=\deg(4)=\deg(5)=1$, as required.

Check: the only sequence with two copies of $1$, one copy of $2$, and first entry $2$ is $2,1,1$, so direct enumeration also gives one tree.

A position requirement can also make a count zero. For the same five labels, instead require $\deg(1)=3$, $\deg(2)=1$, and entry $2$ in position $1$. The degree condition for label $2$ requires $a_2=1-1=0$, while the fixed position requires one occurrence of $2$. Thus $r_2=1>a_2=0$, so $c_2=-1$. The requirements are incompatible and the count is zero.

Several Fixed Entries and a Six-Label Count

Worked Example: Two Prescribed Positions on Six Labels

Let $V=\{1,2,3,4,5,6\}$. Count the trees with degrees $\deg(1)=3$, $\deg(2)=2$, $\deg(3)=2$, and $\deg(4)=\deg(5)=\deg(6)=1$, subject to code position $1$ being $2$ and code position $4$ being $3$.

The code length is $L=6-2=4$. The required occurrence counts are $a_1=3-1=2$, $a_2=2-1=1$, $a_3=2-1=1$, and $a_4=a_5=a_6=1-1=0$. The two fixed entries use one copy each of $2$ and $3$, so $c_1=2$, $c_2=1-1=0$, $c_3=1-1=0$, and $c_4=c_5=c_6=0$. Here $M=4-2=2$, and the total remaining constrained occurrences are $2$, giving $R=2-2=0$. The formula yields

\frac{2!}{0!\,2!\,0!\,0!\,0!\,0!\,0!}\,0^0=1.

The unique code is $2,1,1,3$. Decoding it gives edges $42,21,51,13,36$. Indeed, the first code entry $2$ joins the smallest absent label $4$ to $2$; the next entry $1$ joins $2$ to $1$; the next $1$ joins $5$ to $1$; the final code entry $3$ joins $1$ to $3$; and the last two labels $3,6$ are joined. The resulting degrees are $3$ at label $1$, $2$ at labels $2$ and $3$, and $1$ at labels $4,5,6$.

Check: positions $1$ and $4$ are fixed as $2$ and $3$; the two middle positions must supply the two remaining copies of $1$. There is exactly one way to fill them, namely $1,1$, confirming the count.

When several positions are prescribed, count each fixed occurrence before filling the other positions. If the same label is prescribed at two different positions, those are two occurrences, not one. Conversely, a label prescribed at a position despite having required occurrence count zero makes the count zero immediately.

Common Pitfalls and Why the Translation Helps

Confusing degree with code occurrences. The relation is $\deg(i)=1+$ (number of occurrences of $i$), not equality between degree and occurrence count. For instance, in the five-label example, $\deg(1)=3$ requires two copies of $1$, not three. Counting three copies would demand a code of length at least $3+1=4$ once the required copy of $2$ is included, but the actual code length is $5-2=3$; that mistaken translation would falsely suggest impossibility.

Ignoring a prescribed position when counting multiplicities. In the five-label example, the condition that position $1$ is $2$ consumes the one occurrence allowed by $\deg(2)=2$. The remaining code positions cannot contain another $2$. In the six-label example, both fixed entries consume all required copies of $2$ and $3$. Counting the original occurrence totals again among the unfilled positions would overcount or produce an impossible sequence.

The method is useful because it turns tree constraints into elementary sequence counting. The bijection handles the graph structure; after translating degrees and fixed entries, the remaining task is to place specified numbers of symbols into positions. Always check that the code length is $n-2$, that each required occurrence count is degree minus one, and that the fixed entries do not exceed those counts.

Check Your Understanding

For each question, treat a prescribed code entry as an exact requirement at the stated position.

On $V=\{1,2,3,4\}$, how many trees have $\deg(1)=3$ and $\deg(2)=1$, with no other degree conditions?
On five labels, how many trees have $\deg(1)=2$, $\deg(2)=2$, and position $2$ equal to $1$?
On six labels, explain why $\deg(4)=1$ and a prescribed code entry $4$ at position $1$ are incompatible.
State the number of code positions remaining after $k$ distinct positions in a Prüfer sequence of a tree on $n$ labels have been fixed.
For the six-label conditions in the worked example, list the two entries that remain after the fixed positions and explain why their order is forced.