((())) | ()(()) | (())() | (()()) | ()()() |

The Catalan numbers count many other types of finite structures, such
as binary trees, planar trees, polygon dissections, and so on. For
want of a better name I shall call them **Catalan structures**. Here
are some examples. To see some examples, choose an order and a type then
click the Display button. (To see them your browser must support at least
version 1.1 of Java.)

In each case, there is a "natural" one-to-one correspondence between the Catalan structures and balanced strings of brackets. Can you find the rule which associates the structure with the balanced string of brackets?

The number of Catalan structures of order 7 is 429 whereas the number of structures of order 8 is 1430. Therefore, in order to keep the display within reasonable limits, I've stopped at 7.

The Java program which controls the display can deal with Catalan structures up to order 19, at which point there are 1 767 263 190 structures. But then the next Catalan number ( 6 564 120 420 ) exceeds the capacity of a Java integer.

Last changed: 17 November 1999

Don Taylor