Catalan numbers: Number of different arrangements for 2 different kinds of parentheses

Question

Let's say I have () and [] for parentheses. How many different balanced arrangements do I have for them? I know how to calculate with 1 type of parentheses but not for more than 1. In general, for n different kinds of parentheses, how do I calculate the different balanced arrangements?

Answer 1

If you only require that the parentheses and square brackets be balanced independently, so that ([)] counts as balanced, it’s not too hard. Say that you have $m$ pairs of parentheses and $n$ pairs of square brackets. There are $C_m=\frac1{m+1}\binom{2m}m$ balanced strings of the parentheses and $C_n=\frac1{n+1}\binom{2n}n$ balanced strings of the square brackets, and you can interlace the two strings arbitrarily to form a string of length $2m+2n$. There are $\binom{2(m+n)}{2m}$ ways to choose which $2m$ positions in the string get the parentheses, so there altogether

$$C_mC_n\binom{2(m+n)}{2m}=\frac1{(m+1)(n+1)}\binom{2m}m\binom{2n}n\binom{2(m+n)}{2m}$$

of these weakly balanced strings. The total number of weakly balanced strings of length $2\ell$ is then

$$\sum_{m=0}^\ell C_mC_{\ell-m}\binom{2\ell}{2m}\;.$$

If we require the stronger kind of balancing, the calculation is rather different and, perhaps surprisingly, a good bit nicer. We can start with any of the $C_\ell$ balanced strings of square brackets and then simply choose $m$ of the balanced pairs to convert to parentheses. That can be done in $\binom{\ell}m$ ways, so we get a total of

$$C_\ell\binom{\ell}m=\frac1{\ell+1}\binom{2\ell}\ell\binom{\ell}m$$

of these strongly balanced strings with $m$ pairs of parentheses and $n=\ell-m$ pairs of square brackets, and the grand total is then

$$C_\ell\sum_{m=0}^\ell\binom{\ell}m=2^\ell C_\ell=\frac{2^\ell}{\ell+1}\binom{2\ell}\ell\;.$$