might be easier to consider that the sequence actually has length , but it’s just that the last value is always guaranteed to be so it’s typically just discarded
note while constructing: a leaf always exists by pigeon-hole principle because there are elements and possible values so at least one value must not appear
Fun exercise: you have trees in a labeled forest, each tree with size . how many ways are there to join this forest into a single tree by adding edges?
Note that in this variation, the information stored in our Prufer sequence is insufficient to reconstruct the entire tree. In particular, when we select a leaf, we only know which component to select but not necessarily which vertex to pick. Now note that each component is selected as a leaf exactly once, so our final answer is just