Problem:
How many labeled rooted trees are there on 12 nodes where no node has exactly 4 children.
I thought to use the principle of inclusion-exclusion. Let $N_i$ be the set of rooted labeled trees with exactly $i$ nodes with 4 children?
Since there can be at most 2 nodes with exactly four children, by the principle of inclusion exclusion we have
$$ \#(\text{labeled rooted trees with no nodes with 4 children}) = $$ $$\#(\text{labeled rooted trees}) - |N_1| - |N_2| + |N_1 \cap N_2| $$
Thus $$ \#(\text{labeled rooted trees with no nodes with 4 children}) = n^{n-1} - |N_1| - |N_2| + |N_1 \cap N_2| $$
My problem is actually computing $|N_1|$, $|N_2|$ or $|N_1\cap N_2|$. How do I find these?
Also, if there is a better way to approach this I'm all ears.
Thanks!
I do not think you are applying the principle of inclusion exclusion quite correctly.
Let $E_i$ be the set of trees where vertex $i$ has exactly four children. According to the principle of inclusion exclusion, the number of rooted trees where no vertex has four children is $$ 12^{12-1}-\sum_{i=1}^{12} |E_i|+\sum_{1\le i<j\le 12}|E_i\cap E_j| $$ To count $|E_i|$, use Prufer codes. Rooted trees are in bijection with lists of length $n-1$ of labels of vertices, and the number of times each vertex appears equals the degree of that vertex in the corresponding tree. Therefore, you want to count strings of length $12-1=11$ where the element $i$ appears exactly four times. The number of these is $\binom{11}411^{7}$; choose the locations of the $i$'s, then assign the other seven entries to be anything except $i$. Finally, to count $|E_i\cap E_j|$, both $i$ and $j$ must appear exactly four times, which can be done in $\binom{11}4\binom{7}410^3$ ways. Putting this all together, the answer is $$ 12^{11}-\binom{12}1\binom{11}411^7+\binom{12}2\binom{11}4\binom7410^3 $$