Proving number of leaves in $m$-ary tree.

Question

Prove that a full $m$-ary tree with $i$ internal vertices has $l=(m-1)i +1$ leaves. I'm having trouble finding any good information about $m$-ary trees online I've got a few pictures but they don't seem to have any consistency.

Answer 1

An $m$-ary tree is a recursively defined structure as an external node or an internal node that is connected to $m$-ary trees. If we denote by $T$ the class of trees $m$-ary, this definition translates into the following relationship:

$$T = \{•\} + \{◦\} × \underbrace{T × T · · · × T}_{m}$$

Applying the symbolic method, we have that the generating function that counts the number of $m$-ary trees with $n$ internal nodes satisfies the equation:

$$T(t) = 1 + T(t)^m.$$

To extract the coefficient, proceed as follows: $$T(t) − 1 = tT(t)^m,\quad T_0 = 1$$ $$A(t) = t(1 + A(t))^m,\quad A(t) = T(t) − 1$$ $$T_i = A_i =\frac{1}{i}[u^{i−1}](1 + u)^{mi} =\frac{1}{i}\binom{mi}{i − 1}= \frac{1}{(m − 1)i + 1}\binom{mi}{i}.$$

Let $B(t, w)$ be the bivariate generating function in which $t$ counts the internal nodes and $w$ the external nodes. Applying the symbolic method in this case we have the following functional equation: $$B(t, w) = w + tB(t, w)^m$$

Setting $A(t, w) = B (t, w) −1$ we have $A (t, w) = t (A (t, w) + w)^m$, and we are therefore in the condition of being able to apply the Lagrange inversion formula with $φ(u) = (u + w)^m$

\begin{align*} [t^i]A(t, w) &= \frac{1}{i}[u^{i−1}](u + w)^{mi}\\ &=\frac{1}{i}[u^{i−1}]w^{mi} \left(1 +\frac{u}{w}\right)^{mi}\\ &=\frac{1}{i}w^{mi}\binom{mi}{i − 1}\left(\frac{1}{w}\right)^{i−1}\\ &=\frac{1}{i}w^{mi-i+1}\binom{mi}{i − 1}\\ &=\frac{w^{(m-1)i+1}}{(m-1)i+1}\binom{mi}{i} \end{align*} $$$$

This tells us that $m$-ary trees with $i$ internal nodes have exactly $l=(m - 1) i + 1$ external nodes.