Counting trees
Tonight's idea
A tree joins \(n\) towns with \(n - 1\) roads, with a route between any two towns and no loops. Label the towns 1 to \(n\). How many trees are there? Cayley's formula says \(n^{n-2}\). The proof is a code, named after Prüfer.
Encode. Find the leaf (a town with only one road) with the smallest label. Write down its neighbour, then delete the leaf and its road. Repeat until two towns are left. You have written \(n - 2\) numbers, each from 1 to \(n\).
Decode. A town with \(d\) roads is written \(d - 1\) times, so the labels missing from the code are the leaves. List the towns 1 to \(n\). Join the smallest listed town that is not in the code to the first number in the code. Cross that town off the list and that number off the code. Repeat. When the code is empty, join the two towns left.
Decoding undoes encoding, so each tree has one code and each code has one tree. There are \(n^{n-2}\) codes, so there are \(n^{n-2}\) trees.
Watch one: six towns
The leaves are 1, 2, 3 and 6.
Delete 1, write 4. Delete 2, write 4. Now 4 is a leaf. Delete 3, write 5. Delete 4, write 5. Towns 5 and 6 are left, so stop: the code is \((4, 4, 5, 5)\).
Decode to check. Towns 1, 2, 3, 6 are missing. Join 1–4, then 2–4. The code left is \((5, 5)\), so 4 is now free, but 3 is smaller: join 3–5, then 4–5. Towns 5 and 6 remain: join them. The same five roads.
Your turn
- Four towns. Encode the path 3–1–4–2 and the star with town 2 in the middle. Check both against the figure.
- Five towns. Decode \((2, 5, 2)\) and draw the tree. Which town has three roads, and how could you tell from the code?
- Five towns give \(5^3 = 125\) trees. A star has code \((a, a, a)\). A path has three different numbers in its code. Count the stars, count the paths, and so count the trees of the only other shape. Draw that shape.
- Six towns give \(6^4 = 1296\) trees. In how many is town 1 a leaf? In how many does town 6 have exactly three roads?
Stretch: how leafy is a random tree?
Pick one of the \(n^{n-2}\) trees at random. Show that the chance town 1 is a leaf is \(\left(1 - \tfrac1n\right)^{n-2}\). Evaluate it for \(n = 6\). What number does it approach as \(n\) grows? (Grade 10 met \(\left(1 + \tfrac1n\right)^n \to e\).)
Answers
- Path 3–1–4–2: the leaves are 2 and 3. Delete 2, write 4. Delete 3, write 1. Code \((4, 1)\). Star: delete 1, write 2; delete 3, write 2. Code \((2, 2)\). Both match the figure.
- Towns 1, 3, 4 are missing. Join 1–2. The code left is \((5, 2)\); join 3–5. The code left is \((2)\); the smallest free town is 4, so join 4–2. Towns 2 and 5 remain: join 2–5. Roads: 1–2, 4–2, 2–5, 5–3. Town 2 has three roads, because it appears twice in the code and \(d - 1 = 2\).
- Stars: 5, one for each choice of \(a\). Paths: \(5 \times 4 \times 3 = 60\). The rest: \(125 - 5 - 60 = 60\). Their codes have one number twice and another once, so one town has three roads and one has two: a path of four towns with one extra road from a middle town to the fifth town, like the letter T with a long arm. (Check: 5 choices for the doubled number, 4 for the single one, 3 orders, \(5 \times 4 \times 3 = 60\).)
- Town 1 is a leaf when 1 is missing from the code: each of the four entries is one of the other 5 labels, so \(5^4 = 625\). Town 6 has three roads when 6 appears exactly twice: choose its two positions in 6 ways and fill the other two with any of 5 labels, \(6 \times 5^2 = 150\).
Stretch. Town 1 is a leaf when none of the \(n - 2\) entries is 1. That is \((n-1)^{n-2}\) codes out of \(n^{n-2}\), a fraction \(\left(1 - \tfrac1n\right)^{n-2}\). For \(n = 6\): \((5/6)^4 = 625/1296 \approx 0.48\). As \(n\) grows it approaches \(1/e \approx 0.37\), because \(\left(1 - \tfrac1n\right)^n \to 1/e\) and the two extra factors approach 1. In a large random tree about 37% of the towns are dead ends.