A vertex that is not a leaf
Consider all trees on the labelled vertex set (there are of them by Cayley's formula). In how many of these trees is vertex not a leaf (its degree is at least )?
Show hints (3)+
- Which labelled trees encoding counts every tree exactly once?
- In the Prüfer sequence a vertex appears (degree minus one) times.
- Count trees where label 1 never appears, then complement.
Answer
Reveal answer →Final answer
9031
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading, Systematic & Data-Driven Trading