The Catalan numbers Cn have a very large number
of combinatorial interpretations (see for example
R. P. Stanley, Enumerative Combinatorics,
Vol. 2, Problem 6.19).
This illustration shows three of them.
- (a) The number of ways of dissecting a convex polygon
of n+2 sides into n triangles by drawing
n-2 nonintersecting diagonals.
- (b) The number of planar binary rooted trees with n nodes.
- (c) The number of planar planted trees with n+1 nodes.