# Balanced parentheses and associating a binary operation

It is well known that the Catalan number $$C_n$$ counts the number of expressions containing $$n$$ pairs of parentheses which are correctly matched, e.g. $$((()))\qquad ()(())\qquad ()()()\qquad (())()\qquad (()())$$ It is also known that $$C_n$$ is the number of different ways $$n+1$$ factors can be completely parenthesized, e.g. $$((ab)c)d\qquad (a(bc))d\qquad (ab)(cd)\qquad a((bc)d)\qquad a(b(cd))$$ My question: Is there is a direct way to parenthesized expressions with $$n+1$$ factors from the balanced parentheses expressions? To sharpen my question, if we know for example that $$(())\qquad()()$$ are the number of balanced parentheses expressions with $$2$$ pairs of parentheses, then how to parenthesized $$abc$$ from these expressions?

I will refer to strings like ()() and (()) as Dyck words. The goal is, given a Dyck word with $$n$$ pairs of parentheses, find a parenthesization of $$a_1\;a_2\;\dots\;a_{n+1}$$ Here is a recursive procedure to do this.

• For the base case, the empty Dyck word corresponds to the single-term expression $$a_1$$.

• Let $$D$$ be the given Dyck word. Write $$D=\color{red}(\,D_1\,\color{red})\,D_2$$ where $$\color{red}(\color{red})$$ is the matching parentheses pair including the leftmost open paren. It follows that $$D_1$$ and $$D_2$$ are smaller Dyck words.

• Suppose that $$D_1$$ has $$k$$ pairs of parentheses. Recursively apply this bijection to find the parenthesization $$P_1$$ of $$a_1,\dots,a_{k+1}$$ corresponding to $$D_1$$. Similarly, use $$D_2$$ to parenthesize the remaining terms $$a_{k+2},\dots,a_{n+1}$$, and call this $$P_2$$.

• Enclose both of $$P_1$$ and $$P_2$$ in a extra pair of parentheses (exception: if $$P_1$$ or $$P_2$$ is a single term, omit this step), and then concatenate the results.

Example: Let $$D=$$ ()(()). We first write this as $$D= \color{red}(\varnothing\color{red})(())$$ so $$D_1$$ is the empty Dyck word, and $$D_2$$=(()). This means that $$P_1=a_1$$, and $$P_2$$ is the parenthesization of $$a_2\;a_3\;a_4$$ derived from (()).

We further split $$D_2=\color{blue}(()\color{blue})\varnothing$$ so $$D_2$$ splits as $$D_{2,1}$$=() and $$D_{2,2}=\varnothing$$. Recursively, $$D_{2,2}$$ corresponds to the expression $$a_4$$, using only the last variable, while $$D_{2,1}$$ will determine the way for the first two remaining variables $$a_2$$ and $$a_3$$, which must simply be $$a_2a_3$$. We enclose this latter expression in parentheses, since it has length at least $$2$$.

Therefore, $$P=P_1P_2=a_1(P_{2,1}P_{2,2})=a_1((a_2a_3)a_4)$$