1) How many trees on these vertex have at least 2 leaves ?

2) How many trees on these vertex have more than 2 leaves ?

Attempt -

I will use inclusion-exclusion for both cases -

$1)$ $$\binom{8}{2}\cdot6^6-\binom{8}{3}\cdot5^6 + \binom{8}{4}\cdot4^6 - \binom{8}{5}\cdot3^6 + \binom{8}{6}\cdot2^6 - \binom{8}{7}$$

I exclude from the "universe" where 2 of my vertices are leaves.

2) My problem now is when I have at least 3 leaves, and using the same method $$\binom{8}{3}\cdot5^6 - \binom{8}{4}\cdot4^6 +\binom{8}{5}\cdot3^6 -\binom{8}{6}\cdot2^6 + \binom{8}{7}$$

Is everything true ? thank you !

  • $\begingroup$ I am not sure I understand how you get your formula. $\endgroup$ – Arnaud Mortier Feb 10 '18 at 16:59

By definition, a tree is connected, and it is a classical result that a tree with at least two vertices has at least two leaves.

Hence 1. is simply asking for the total number of trees on $8$ vertices, given by Cayley's formula:


Now a tree has exactly two leaves if and only if it is linear, and such trees almost correspond to permutations on $8$ elements, the only caveat is that each tree corresponds to two permutations (since the trees are not supposed to be oriented). Hence there are $$\dfrac{8!}{2}$$ such trees, and so $$8^6-\dfrac{8!}{2}=241984$$ trees with more than $2$ leaves.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.