0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Element118
    Nov 6, 2015 at 14:11
  • $\begingroup$ can i answer $n_0$? $\endgroup$
    – JMP
    Nov 6, 2015 at 14:16
  • $\begingroup$ 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? $\endgroup$
    – soulless
    Nov 6, 2015 at 14:20

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

node/child graphs

$\endgroup$
2
  • $\begingroup$ What do you mean by ignoring n-1?? i also don't understand what α and 223346 are referring to here.... What i have concluded so far is total number of nodes should be total number of edges + 1, while total nodes with children = n1 + n2 +..nm the difference of both with be number of nodes without children, am i right? $\endgroup$
    – soulless
    Nov 6, 2015 at 17:25
  • $\begingroup$ typo - i meant to use _ - fixed $\endgroup$
    – JMP
    Nov 6, 2015 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .