---
title: "Counting Trees: Cayley and Prüfer"
summary: n^(n-2) labelled trees, the bijection that proves it, and what the degree sequence looks like from the code.
difficulty: hard
tags: [counting, bijection, trees]
see: [proofs/double-count, matrices/matrix-tree]
---

:::theorem title="Cayley's formula"
The number of trees on the labelled vertex set $\{1, \dots, n\}$ is $n^{n-2}$.
:::

Three proofs exist in the wild; only one is useful in a contest, because it also *generates* and *decodes*.

## The Prüfer code
:::definition label="Encoding"
Given a labelled tree, repeat until two vertices remain: output the label of the **smallest leaf**, delete it, and decrease the degree of its neighbour. The output is a sequence of $n-2$ numbers in $[1,n]$.
:::

:::theorem title="Bijection"
The map above is a bijection between labelled trees on $n$ vertices and all $n^{n-2}$ sequences of length $n-2$ over $[1,n]$.
:::

:::proof
Construct the inverse: given $P = (p_1, \dots, p_{n-2})$, set $\deg(v) = 1 + \#\{i : p_i = v\}$. For $i = 1 \dots n-2$: let $v$ be the smallest label with $\deg(v) = 1$; emit the edge $v \to p_i$; set $\deg(v) := 0$, $\deg(p_i) := \deg(p_i) - 1$. Finally connect the two labels that still have $\deg = 1$.
Well-defined: at each step the remaining degree sum is $\sum (1 + \text{occurrences left}) = $ (number of remaining vertices) + (remaining sequence length) $= k + (k - 2) > k - 1$, so at least two vertices have degree 1 — a leaf always exists.
Round-trip: decoding rebuilds exactly the deletions in order, because both procedures pick "smallest vertex whose remaining degree is 1" at the same moments; encoding a decoded tree recovers $P$ since each emitted edge's non-leaf endpoint is $p_i$. Counting: $n$ choices per position, $n-2$ positions. ∎
:::

```cpp prufer.cpp
// encode: O(n log n) with a set of leaves
vector<int> prufer_encode(int n) {
    multiset<int> leaves;
    for (int v = 1; v <= n; v++) if (deg[v] == 1) leaves.insert(v);
    vector<int> p;
    vector<int> d = deg, par(n + 1);
    set<int> alive;
    for (int v = 1; v <= n; v++) alive.insert(v);
    while ((int)p.size() < n - 2) {
        int v = *leaves.begin(); leaves.erase(leaves.begin());
        int u = neighbour_of(v);                  // the unique alive neighbour
        p.push_back(u);
        if (--d[u] == 1) leaves.insert(u);
        alive.erase(v);
    }
    return p;
}
```

## What the code makes trivial
:::props title="Corollaries you can read off the sequence"
- $\deg(v) = 1 +$ (number of times $v$ appears in the code) — the standard solution to "reconstruct the tree from its degrees".
- Number of trees where **vertices $1..k$ are leaves**: sequences avoiding $1..k$ $= (n-k)^{n-2}$.
- Number of **spanning trees of $K_{a,b}$**: $a^{b-2} b^{a-2}$ — count sequences whose positions split by part, or use @matrices/matrix-tree.
- Probability a fixed vertex has degree $d$ in a random tree: $\binom{n-2}{d-1} (1/n)^{d-1} (1-1/n)^{n-1-d}$ — binomial, so degrees concentrate near 1.
- Rooted labelled trees: $n^{n-1}$ (multiply by $n$ choices of root). Ordered (plane) trees with $n$ vertices: Catalan $\frac{1}{n}\binom{2n-2}{n-1}$ — a different object; don't mix them up.
:::

:::example title="Reconstruct from degrees (classic)"
Given degrees $d_1, \dots, d_n$ with $\sum d_i = 2n-2$, output any tree. Run the decode direction: push every vertex $i$ exactly $d_i - 1$ times into a queue, keep a min-heap of "still has zero copies used and degree 1", attach greedily. $O(n \log n)$, and it is exactly Prüfer decoding with the multiset precomputed.
:::

:::figure src="Simple_Rooted_Tree.svg" caption="Rooting multiplies the count by n — one choice per tree — which is why n^(n-1) counts rooted labelled trees."
:::

## When counting is modulo a prime
Contest versions ask for $n^{n-2} \bmod p$. Two cautions:
1. $n$ can be $10^9$, so use fast power; if $p$ is not prime, Euler's theorem needs $\gcd(n,p)=1$.
2. "Count trees with additional constraints" (degree upper bound, prescribed diameter) is usually *not* Prüfer-friendly except via generating functions: prescribe degrees exactly → multinomial $\frac{(n-2)!}{\prod (d_i - 1)!}$.

:::problems
- [[CSES 1134]] Prüfer Code | https://cses.fi/problemset/task/1134 | core | decoding
- [[CF 9D]] How many trees? | https://codeforces.com/problemset/problem/9/D | hard | DP, Catalan-ish
- [[SPOJ HIGHWAYS]] Counting Highways | https://www.spoj.com/problems/HIGHWAYS/ | hard | matrix-tree theorem
:::