Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Can't you just reverse the construction? –  Yuval Filmus Jan 5 '11 at 7:15
add comment

1 Answer

up vote 4 down vote accepted

Knuth covers this in chapter 7.2.1.6 (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 http://cs.utsa.edu/~wagner/knuth/fasc4a.pdf for more details.

share|improve this answer
add comment

Your Answer

 
discard

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.