Number of ways of paranthesing n applications of a binary operator

Question

Let's assume I have four elements a,b,c,d. Number of ways to multiply them : (((a.b).c).d), ((a.(b.c)).d), ((a.b).(c.d)) , (a.((b.c).d)) and (a.(b.(c.d)))) is five, which is the catalan number C3. I want to turn this problem into how many valid parentheses can be written problem (for n=3) by dropping the left parantheses and letters from the above terms and replacing the dots with new left parantheses. In the end I have ((())), (()()), (())(), ()(()), ()()() . The problem is I could not find a way to transform back these pair of parantheses into binary multiplication form of a,b,c,d which was in the beginning.

Answer 1

One way is to use the set of full binary trees (each vertex has two children or no children) with $n+1$ leaves, where $n+1$ is the number of elements being multiplied. You have a valid string of $n$ pairs of parentheses. Start by drawing the root of the tree. (I draw my trees with the root at the top.) Now scan the parenthesis string from left to right. When you encounter a left parenthesis, draw an edge down to a left child, and when you encounter a right parenthesis, back up the tree until you can draw an edge to a right child, and then draw that edge.

Suppose that you start with the string ()(()). Then the stages of building the tree are as follows:

       *          *           *           *           *           *  
      /          / \         / \         / \         / \         / \  
     *          *   *       *   *       *   *       *   *       *   *  
                               /           /           /           / \  
                              *           *           *           *   *  
                                         /           / \         / \  
                                        *           *   *       *   *  
      (          ()          ()(        ()((        ()(()       ()(())

Now replace the leaves, from left to right, with the elements being multiplied:

     *  
    / \  
   a   *  
      / \  
     *   d  
    / \  
   b   c  

Finally, treat the internal vertices as multiplication operations and parenthesize according to the tree structure to get

$$\color{blue}(a\cdot\color{crimson}((b\cdot c)\cdot d\color{crimson})\color{blue})\;.$$