Catalan Structures

The number of "balanced" strings of n left and n right brackets is the Catalan number c[n] of order n. For example, the Catalan number of order 3 is 5. That is, c[3] = 5 and we have 5 balanced strings:

((()))

()(())

(())()

(()())

()()()

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.)

The Catalan structures applet should display here.

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