I got the following puzzle -
count the number of different sequences with
$r$ - "$($" and $r$ - "$)$",
$k$ - "$[$" and $k$ - "$]$",
$n$ - "{" and $n$ - "}"
I know that this is solved with Catalan numbers and know that the number of balanced sequences with "(" and ")" is $${\frac {1}{n+1}}{2n \choose n}$$
But how to solve it when I got 3 types of objects?
Edit: ((({)[])}) is valid expression.
Thanks for any Tips and guidance...
There are $c_r \times c_k \times c_n$ triples of balanced (), [], and {} expressions of the appropriate lengths. Now you have to interleave them. There are $2(r+k+n)$ positions, $2r$ of which have to be occupied by (), and so on. Thus, there are $\binom{2(r+k+n)}{2r}$ ways to place the () symbols. Having done that, there are $2(k+n)$ positions, $2k$ of of which have to be []. Surely you can finish from here?
The key here is that the 3 symbol sets are disjoint, so given one of your expressions you can uniquely parse it into the 3 balanced (), [], and {} expressions.
For example, suppose $r=k=1$ and $n=0$. The Catalan numbers are all 1 in this case, so in this case the question boils down to counting the number of ways of interleaving () with []. There are 4 ($2r+2k+2n=4$) positions in this case, two of which will end up holding () and 2 holding []. Thus, letting 0 and 1 stand for "this position will hold part of ()" and "...part of []" respectively, we have patterns 0011, 0101, 0110, 1001, 1010, and 1100: six in all, counted by $\binom{4}{2}$, resulting in interleavings ()[], ([)], ([]), [()], [(]) and $\text{[]()}$. You get to specify an arbitrary size $2r$ subset of the available $2r+2k+2n$ positions (in $\binom{2r+2k+2n}{2r}$ ways to fill in your () pattern in $c_r$ ways. Then you get to pick an arbitrary size $2k$ subset of the unoccupied $2k+2n$ positions, in $\binom{2k+2n}{2k}$ ways and fill those positions with [] expressions in $c_k$ ways. Now you have only $2n$ remaining slots, with no futher choices of subsets, but $c_n$ ways to fill them with {} expresions. The interleaving part of the problem is a "subset counting" problem, not a "gaps" or "stars and bars" problem.