1
$\begingroup$

I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e., $$ \mu_{n}^{(m)} = \frac{\# \text{full nodes in all $m$-ary trees having $n$ nodes} }{\# \text{nodes in all $m$-ary trees having $n$ nodes}}$$.

As to the denominator, according to this answer, it sholud be given by $$n C_m^n = \binom{mn}{n} \frac{n}{(m-1)n + 1}$$ As to numerator, at the first glance, I tought that this answer would have provided a hint; but then I have realized that it is not the case because it gives how many trees have $n$ full nodes, but I need to know how many full nodes are in the set of all the $m$-ary trees having $n$ nodes.

Could someone help me to understand how to solve it and provide (if any) a usable formula for $\mu_{n}^{(m)}$?

$\endgroup$
1
$\begingroup$

Every $m$-ary tree is a node together with up to $m$ children, which are also $m$-ary trees. Let $T(x,y)$ be the generating function in which the coefficient of $x^ny^k$ is the number of $m$-ary trees with $n$ nodes and $k$ full nodes. Then $$ T(x,y) = x(1 + T(x,y) + \cdots + T(x,y)^{m-1} + yT(x,y)^m). $$ The generating function of the total number of $m$-ary trees is $A(x) = T(x,1)$, and the generating function of the total number of full nodes in $m$-ary trees is $B(x) = \frac{\partial}{\partial y} T(x,y)|_{y=1}$.

The generating function $A(x)$ satisfies the equation $$ A(x) = x(1 + A(x) + \cdots + A(x)^m). $$ The generating function $B(x)$ satisfies the equation $$ B(x) = x(B(x) + 2A(x)B(x) + 3A(x)^2B(x) + \cdots + mA(x)^{m-1}B(x) + A(x)^m), $$ and so $$ B(x) = \frac{xA(x)^m}{1-x(1+2A(x)+3A(x)^2+\cdots+mA(x)^{m-1})}. $$

You can try solving these equations.

For example, in the trivial case $m=1$, we have $A(x) = x(1 + A(x))$, and so $$ A(x) = \frac{x}{1-x} = \sum_{n \geq 1} x^n. $$ It follows that $$ B(x) = \frac{x\cdot \frac{x}{1-x}}{1-x} = \frac{x^2}{(1-x)^2} = \sum_{n \geq 1} (n-1)x^n. $$ Therefore the average number of full nodes in $1$-ary trees with $n$ nodes is $\frac{n-1}{1} = n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.