Tree. Number of nodes and children

Question

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have NO child are there in $T$?

I have no clue of how to solve it. Please help. Is there anyway i can know total number of nodes here?

Answer 1

HINT: The information given in the problem allows you to calculate the number of edges in $T$ in terms of the numbers $n_1,n_2,\ldots,n_m$. Since $T$ is a tree, the number of edges tells you the number of vertices. You know (in terms of $n_1,n_2,\ldots,n_m$) how many of those vertices have children, so you can calculate the number that have no children.

Answer 2

We can ignore $n_1$ as it doesn't change anything.

The formula is: $$n_0=\sum_\limits{i=2}^k (i-1)\alpha_i +1$$

For example, let $\alpha=\{2,2,1,0,1\}$, whichever way you arrange $223346$, you end with $1\cdot2+2\cdot3+3\cdot4+5\cdot6+1=15$ leaf nodes.