Lesson 5

Trees. In the problem about the number of \(E(n)\) rooted trees with \(n\) edges, we can reason as follows. Consider the leftmost edge \(\{r,v\}\) from the root \(r\) to the vertex \(v\). Some number \(l\) of the remaining \(n-1\) edges will fall into the subtree with the root \(v\).

In the problem about the number \(B(n)\) of rooted binary trees with \(n\) leaves, the required recurrence relation is straightforward: \(l\) leaves fall into the left subtree, and \((n-l)\) into the right subtree. Therefore \(B(n)=C(n-1)\).

There is also a natural bijection between such trees and ways to place parentheses in a product of \(n\) factors.

Finally, a bijection can be established between triangulations of an \((n+1)\)-gon and binary trees with \(n\) leaves as follows.