Lesson 4

Associative Products. In the problem of counting the number of ways \(T(n)\) to parenthesize a product of \(n\) factors, it is also easy to see the familiar recurrence relation: the last (or outermost) operation splits the sequence into \(l+r=n\) factors. Thus, \[T(n)=\sum_{l=1}^{n-1}T(l)T(n-l) \ .\] We conclude that \(T(n)=C(n-1)\).

Moreover, we can observe a bijection between the ways to parenthesize and the triangulations of an \((n+1)\)-gon. On all sides of the \((n+1)\)-gon except one, assign variables \(x_{1}, \dotsc, x_{n}\). Then each diagonal naturally corresponds to an intermediate result of computation, while the remaining side corresponds to the final result. It is easy to see that triangulation determines the parenthesization.