# Tree. Number of nodes and children

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?

• So that is to say, you want to count the number of leaf nodes. Consider the total number of nodes that are the child of another node. Can you count this value in 2 ways? Nov 6, 2015 at 14:11
• can i answer $n_0$?
– JMP
Nov 6, 2015 at 14:16
• What do you mean by 2 ways? the total number of nodes that are the child of another nodes should be 1 + 2 +....+ m right? but what is the use of this? Nov 6, 2015 at 14:20

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.
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.