Balanced parentheses and associating a binary operation

combinatorics

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?

Best Answer

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

Related Question