Counting Labeled Trees with Degree Constraints
A combinatorics problem asks for the number of labeled trees on vertex set {1,2,...,n} in which vertex 1 has degree 1 and vertex 2 has degree 3. A student proposes using Cayley's formula n^{n-2} and then dividing by something, but gets confused. You recall the Prüfer code bijection: labeled trees on n vertices correspond to sequences of length n-2 with entries from {1,...,n}. In this code, the degree of a vertex v equals 1 plus the number of times v appears in the sequence. You need to count sequences of length n-2 over an alphabet of size n such that the symbol 1 appears 0 times and the symbol 2 appears exactly 2 times (since degree 3 means 2 appearances). You must also consider whether n is large enough for such a tree to exist, and handle the case where vertex 1 and vertex 2 are the same (they are not). You decide to count directly and verify with a small case.
1. For general n ≥ 4, derive a formula for the number of such trees using Prüfer sequences. Explain each factor in your count.
Read the worked answer
In the Prüfer code of length n-2, the degree of vertex v is 1 + (number of occurrences of v). So degree 1 for vertex 1 means 0 occurrences; degree 3 for vertex 2 means 2 occurrences. We need sequences of length n-2 over {1,...,n} with no 1's and exactly two 2's. Choose the positions for the two 2's: C(n-2, 2) ways. The remaining (n-2)-2 = n-4 positions must be filled with symbols from {3,4,...,n}, which has n-2 symbols, with repetition allowed. So there are (n-2)^{n-4} ways. Thus total = C(n-2, 2) · (n-2)^{n-4}. This formula is valid for n ≥ 4; for n=4, n-4=0, and (n-2)^0=1, giving C(2,2)=1 tree. Check n=4: vertices {1,2,3,4}, need deg(1)=1, deg(2)=3. The only tree is the star centered at 2 with leaves 1,3,4? But then deg(2)=3, deg(1)=1, deg(3)=1, deg(4)=1. Yes, that works. Prüfer code length 2, no 1's, exactly two 2's: sequence (2,2). One tree. Formula gives 1. Good.
2. Verify your formula for n=5 by explicit enumeration or by a different counting method. What is the number?
Read the worked answer
For n=5, formula gives C(3,2)·(3)^{1} = 3·3 = 9. Let's verify by another method. We need trees on 5 vertices with deg(1)=1, deg(2)=3. The sum of degrees is 2(n-1)=8. We have deg(1)=1, deg(2)=3, so the remaining three vertices (3,4,5) have degrees summing to 8-1-3=4, each at least 1. The possible degree sequences for (3,4,5) are permutations of (2,1,1) or (2,2,0) but 0 is impossible, or (3,? ) but sum 4 with three positive integers: only (2,1,1). So one of vertices 3,4,5 has degree 2, the other two degree 1. Choose which has degree 2: 3 choices. Now count trees with a given degree sequence. Use Prüfer: length 3, no 1's, exactly two 2's, and the remaining symbol is the degree-2 vertex (since degree 2 means one occurrence). For a fixed choice of the degree-2 vertex, say 3, sequences of length 3 with two 2's and one 3: number = 3! / 2! = 3. So for each of 3 choices, 3 sequences, total 9. Matches formula. Alternatively, construct: vertex 2 connected to 1, and to two of {3,4,5}? But then degrees: if 2 connected to 1 and to two others, say 3 and 4, then deg(2)=3, deg(1)=1, deg(3) at least 1, deg(4) at least 1, deg(5) at least 1. To get sum degrees 8, the remaining edges must connect 3-5 and 4-5? That would give deg(5)=2, deg(3)=2, deg(4)=2, sum too high. Let's not. The Prüfer count is reliable. So 9 trees.