# Dyck words and Catalan numbers

One of the many applications of the $$n$$th Catalan number is to calculate the number of strings consisting of $$n$$ $$X$$'s and $$n$$ $$Y$$'s, such that any prefix of the string will contain at least as many $$X$$'s as $$Y$$'s (Dyck words).

However what if, in general, we want to find the number of strings with $$n$$ pairs of $$X$$ and $$Y$$ along with $$m$$ pairs of $$A$$ and $$B$$, such that for the both the pairs, the inequality holds true?

The answer should be $$C_n^2 \binom{4n}{2n}$$. The internal ordering of the $$AB$$ and the $$XY$$s, is a Catalan number. We then 'riffle' the AB-string and the XY-string. Choosing the positions of the ABs in the string can be done in the binomial coefficient ways.
For general $$m,n$$ then the answer is $$C_m C_n \binom{2m+2n}{2m}$$, as Sam mentioned.
• Note that $C_n^2\binom{4n}{2n}=\frac{(4n)!}{n!^4(n+1)^2}$.
• Per's answer is almost right but he forgot that there are two different parameters $n$ and $m$. Jun 25 at 13:45