# Trees on $\{1,2,3,4,5,6,7,8\}$ with conditions

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 !

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

Hence 1. is simply asking for the total number of trees on $8$ vertices, given by Cayley's formula:
$$8^6=262144$$
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.