\(T\):	set of all binary trees.
\(|t|\):	the number of internal nodes of binary tree \(t\).
leaves(\(t\)):	number of leaves in \(t\).
\(T_N\):	number of binary tree of size \(N\).
\(C_N\):	total number of leaves in all binary trees of size \(N\).

We saw earlier that

\[ \begin{aligned} T(z) &= \sum_{t \in T} z^{|t|} = \sum_{N \ge 0} T_N z^N = \frac{1}{2z} \left(1 - \sqrt{1-4z} \right) \\ T_N &= \frac{1}{N+1} {2N \choose N} \\ \end{aligned} \]

The key is to find the cumulative GF (generating function), \(C(z)\), for the leaves:

\[ \begin{aligned} C(z) &= \sum_{t \in T} \text{leaves}(t) z^{|t|} \\ &= z + \sum_{t_L \in T} \sum_{t_R \in T} \left(\text{leaves}(t_L) + \text{leaves}(t_R)\right) z^{|t_L| + |t_R| + 1} \\ &= z + z \sum_{t_L \in T} \text{leaves}(t_L) z^{|t_L|} \sum_{t_R \in T} z^{|t_R|} + z \sum_{t_R \in T} \text{leaves}(t_R) z^{|t_R|} \sum_{t_L \in T} z^{|t_L|} \\ &= z + 2 z C(z) T(z) \\ C(z) &= \frac{z}{1-2z T(z)} \\ &= \frac{z}{1-2z \frac{1}{2z} \left(1 - \sqrt{1-4z} \right)} \\ &= \frac{z}{\sqrt{1-4z}} \\ &= z \sum_{N \ge 0} {-\frac{1}{2} \choose N} (-4z)^N & \text{binomial theorem} \\ &= z \sum_{N \ge 1} {-\frac{1}{2} \choose N-1} (-4z)^{N-1} & N \text{ to } N-1 \\ &= \sum_{N \ge 1} {-\frac{1}{2} \choose N-1} (-4)^{N-1} z^N \\ \therefore C_N &= {-\frac{1}{2} \choose N-1} (-4)^{N-1} \\ &= \frac{-\frac{1}{2} (-\frac{1}{2}-1) (-\frac{1}{2}-2) \cdots (-\frac{1}{2}-(N-1)+1) }{(N-1)!} (-4)^{N-1} \\ &= \frac{-\frac{1}{2} (-\frac{1}{2}-1) (-\frac{1}{2}-2) \cdots (-\frac{1}{2}-N+2) }{(N-1)!} (-2)^{N-1} 2^{N-1} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-3) }{(N-1)!} 2^{N-1} & \text{distribute }(-2)^{N-1} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-3) }{(N-1)!} \frac{2 \cdot 4 \cdots (2N-2)}{1 \cdot 2 \cdots (N-1)} \\ &= \frac{(2N-2)!}{(N-1)!(N-1)!} \\ &= {2N-2 \choose N-1} & \text{!} \\ \end{aligned} \]

Therefore

\[ \begin{aligned} \frac{C_N}{T_N} &= {{2N-2 \choose N-1} \over \frac{1}{N+1} {2N \choose N}} \\ &= {\frac{(2N-2)!}{(N-1)!(2N-2-N+1)!} \over \frac{1}{N+1} \frac{(2N)!}{N!N!}} \\ &= \frac{(2N-2)!}{(N-1)!(N-1)!} \frac{(N+1)N!N!}{(2N)!} \\ &= \frac{N^2(N+1)}{2N(2N-1)}\\ &= \frac{N(N+1)}{2(2N-1)} \\ \frac{C_N}{T_N} &\thicksim \frac{N}{4} \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 10:34 AM