[This was found in my stack of loose notes from May 2013]
Consider the following problems
- Number of plane binary trees with n end points
- Number valid k-ary parenthesis for a string of n characters?
- Sequence of X and Y such that no initial segment of the sequence has more X than Y.
- Number of path P in the (x,y) plane from (0,0) to (n-1,0) using steps (1,k), where k+1 in S or k = -1, with a total of m-1 steps of the form (1,-1) such that P never passes below the x-axis.
- Number of dissections of a convex (m+1)-gon C into n-m regions, each a k-gon, by drawing diagonals that don’t intersect in their interiors
All these problems can be solved by the sequence known as the Catalan number. The first few numbers in the sequence are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
It can be computed using this formula: