TAOCP 2.3.4.4 Exercise 19
The Prüfer-code framework is correct, but the constraint “exactly $k$ leaves” must be enforced as a surjectivity condition, not as a simple restriction on the alphabet.
Section 2.3.4.4: Enumeration of Trees
Exercise 19. [**] [M24] How many different labeled, oriented trees are there having $n$ vertices, $k$ of which are leaves (have in-degree zero)?
Verified: yes
Solve time: 3m30s
The Prüfer-code framework is correct, but the constraint “exactly $k$ leaves” must be enforced as a surjectivity condition, not as a simple restriction on the alphabet. The earlier argument failed because it allowed vertices outside the leaf set to appear zero times in the Prüfer sequence, which would incorrectly increase the number of leaves.
Step 1. Reduce to ordinary labeled trees
An oriented labeled tree (in the sense of a rooted tree with all edges directed away from the root) is obtained by choosing a root in an ordinary labeled tree on $n$ vertices and orienting all edges away from it. Every unrooted labeled tree admits exactly $n$ choices of root, so
$$ #(\text{oriented labeled trees}) = n \cdot #(\text{unrooted labeled trees}). $$
We first count unrooted labeled trees with exactly $k$ leaves (vertices of degree $1$), then multiply by $n$.
Step 2. Translate the problem to Prüfer codes
A labeled tree on $n$ vertices corresponds bijectively to a Prüfer sequence of length $n-2$ over ${1,\dots,n}$.
Key property:
A vertex is a leaf if and only if it does not appear in the Prüfer sequence.
Thus, if the tree has exactly $k$ leaves, then exactly $k$ labels do not appear in the sequence, and the remaining $n-k$ labels each appear at least once.
Fix a leaf set $L\subseteq {1,\dots,n}$ with $|L|=k$, and let
$$ R = {1,\dots,n}\setminus L,\qquad |R| = n-k. $$
Then the Prüfer sequence must satisfy:
- it has length $n-2$,
- it uses only symbols from $R$,
- every symbol in $R$ appears at least once.
This is exactly a surjection condition from positions to labels in $R$.
Step 3. Count sequences for a fixed leaf set
The number of sequences of length $m=n-2$ over an alphabet of size $r=n-k$ in which every symbol appears at least once is the number of surjections from an $m$-set onto an $r$-set. This is
$$ r!, S(m,r), $$
where $S(m,r)$ is the Stirling number of the second kind.
Hence for fixed $L$,
$$ #(\text{trees with leaf set }L) = (n-k)!, S(n-2,,n-k). $$
Step 4. Choose the leaf set
There are $\binom{n}{k}$ possible choices of the leaf set $L$. Therefore the number of unrooted labeled trees with exactly $k$ leaves is
$$ \binom{n}{k} (n-k)!, S(n-2,,n-k). $$
Step 5. Reintroduce orientation
Each unrooted labeled tree corresponds to exactly $n$ rooted oriented trees by choosing a root. The leaf condition (degree $1$ in the underlying tree) is unaffected by rooting.
Thus the number of labeled oriented trees is
$$ n \binom{n}{k} (n-k)!, S(n-2,,n-k). $$
Final answer
$$ \boxed{,n \binom{n}{k} (n-k)!, S(n-2,,n-k),} $$
Correction of the earlier error
The earlier solution incorrectly replaced the Prüfer condition with “choose any sequence over $n-k$ symbols,” giving $(n-k)^{n-2}$. This overcounts because it allows symbols in $R$ to be absent, which would incorrectly create additional leaves.
The correct condition is that every vertex in $R$ must appear at least once, which converts the problem into a surjection count and introduces Stirling numbers.