Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In an article by Tom Davis on Catalan numbers, Davis mentions several problems that are shown to be equivalent. One of them is the problem of determining the number of strings of $n$ pairs of balanced parentheses. Another is the problem of determining the number of "multiplication orderings" of $n + 1$ numbers. In both cases, the answer to the problem is $C_n$, or the nth Catalan number.

For example, with $n = 3$, there are $C_3 = 5$ different strings of 3 pairs of balanced parentheses:

()()(), ()(()), (())(), (()()), ((()))

With four numbers, there are also $C_3$ multiplication orderings of them:

(((a·b)·c)·d), ((a·b)·(c·d)), ((a·(b·c))·d), (a·((b·c)·d)), (a·(b·(c·d)))

Davis shows how to convert a multiplication ordering of $n + 1$ terms to a string of $n$ pairs of balanced parentheses, but I would like to know how to go the other way; i.e. given a string of $n$ pairs of balanced parentheses, how can I calculate a corresponding multiplication ordering?

share|cite|improve this question
Can't you just reverse the construction? – Yuval Filmus Jan 5 '11 at 7:15
up vote 4 down vote accepted

Knuth covers this in chapter (vol. 4, fascicle 4) of The Art Of Computer Programming, where he talks about generating all trees (which is an essentially equivalent problem) and converting back and forth between representations. Have a look at for more details.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.