How many labeled trees exist on 100 vertices, such that all vertices have degree 1,2 or 3, and there are exactly 32 leaves?

Question

I know Cayley's theorem, but no idea how should i solve this.

If i consider this graph without that 32 leaves, then i have a graph with 68 vertices, and each vertice's degree is 1 or 2?

Answer 1

Cayley's formula says there are $n^{n-2}$ trees on $n$ vertices. This is great, but our problem has more constraints. Luckily for us, there is a stronger result of Cayley's formula, which states: $$\begin{pmatrix}n-2\\ d_1 - 1, d_2 - 1,....,d_n - 1\end{pmatrix}=\frac{(n-2)!}{(d_1 - 1)!(d_2 - 1)!...(d_n - 1)!}$$ Which gives us the number of trees with $n$ vertices with degree $d_n$. You said there are exactly $32$ vertices with degree $1$ (the leaves), which makes this quite a bit easier since if $d_i = 1$ then $(1 - 1)! = 0!=1$. Thus we need to count $$\begin{pmatrix}100-2\\ d_1 - 1, d_2 - 1,....,d_{68} - 1\end{pmatrix}=\frac{(100-2)!}{(d_1 - 1)!(d_2 - 1)!...(d_{68} - 1)!}$$ Furthermore, the same applies to if $d_i = 2$, since $(2-1)!=1!=1$. Thus, we arrive at a final counting function of $$\begin{pmatrix}100-2\\ d_1 - 1, d_2 - 1,....,d_{68-a} - 1\end{pmatrix}=\frac{(100-2)!}{(d_1 - 1)!(d_2 - 1)!...(d_{68-a} - 1)!}$$ Where $a$ is the number of times $2$ appears and $d_{n-a}$ is either of degree $3$ and $a$ is the amount of times we must count the case $d_n = 2$. Also in any graph we have the formula $$\sum_{v_i\in V}deg(v_i) = 2\left | E \right |$$ Or in other words the sum of the degrees of each vertex equals $2$ times the amount of edges. Luckily for us, trees have an even harder definition that $$\left | E \right | = \left | v \right | - 1$$ Or the amount of edges is equal to the amount of vertices minus 1. Now recall that we do not have to count the leaves of the tree in our original counting function, so our tree is a graph with $100$ vertices, thus using our formulas we get $$\sum_{v_i\in V}deg(v_i) = 2\left | v \right |-2=2i-2$$ Therefore, $$\sum_{v_i\in V}deg(v_i) =2(100) - 2 = 198$$ So now we have to find how many distinct ways we can sum $2$ and $3$ together to get $198$ using exactly $68$ $2's$ and $3's$ and $32$ $1's$ to see how many distinct versions of Cayley's formula we need to sum to get our result. In other words we are trying to solve $$2a + 3b + 32 = 198$$ $$a + b + 32= 100$$ So by substitution we get $$2a + 3b= 166$$ $$a = 68 - b$$ Therefore $$2(68-b)+3b=166$$ $$136+b=166$$ $$b=30$$ so $$a+30=68$$ $$a=38$$ Which clearly has only 1 unique positive solution. Now we are ready for a final answer plugging in our $30$ $3's$ and $a=38$ to our counting formula $$\begin{pmatrix}100-2\\ d_1 - 1, d_2 - 1,....,d_{68-a} - 1\end{pmatrix} \rightarrow \begin{pmatrix}(100-2)!\\ d_1 - 1, d_2 - 1,....,d_{30} - 1\end{pmatrix}$$ And, as discussed earlier, $d_n = 3$ for all $n$, so we have $$\frac{(100-2)!}{(3 - 1)!(3 - 1)!(3-1)!...(3-1)!} = \frac{98!}{2!2!2!2!...2!}=\frac{98!}{2^{30}}$$