Count the number of trees with vertex set n 1 2 n and the f

Count the number of trees with vertex set [n] {1, 2, ..., n} and the following property trees have exactly 2 leaves, trees have exactly n - 2 leaves. (You can use the Prufer correspondence or direct counting argument. However, I recommend to do both and make sure you get the same answer.)

Solution

Let S Z with |S| = n 2. Prufer Encoding and Decoding are inverse bi jections between the set of trees with vertex set S and the set of sequences of length n 2 with elements in S.

Proof: We proceed by induction on n. As a base, observe that when n = 2, there is a single sequence of length 0 and a single tree with vertex set S, and the encoding/decoding operations exchange these. For the inductive step, we may assume n 3. Let T be a tree with vertex set S, let a = (a1, . . . , an2) be the encoding of T, and let T 0 be the decoding of a. Let v be the smallest leaf of T. Then, by the encoding process, v is adjacent to a₁, and v is smaller than any other vertex which does not appear in a, since (by the above observation) all such vertices are leaves. It follows from the decoding rules that in the tree T^\' , the vertex v is a leaf adjacent to a1. Now, T v encodes to (a2, . . . , an) which decodes to T^\' v, so by induction T v and T^\' v are the same, and it follows that T and T^\' are the same. To complete the inductive step, we still need to show that every sequence a = (a1, . . . , an2) is the encoding of some tree. To see this, let v S be the smallest element which does not appear in a. Then, by induction (a2, . . . , an2) is the encoding of some tree T with vertex set S \\ {v}, and we find that a is an encoding of the tree obtained from T by adding the vertex v and the edge va₁. This completes the proof.