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.

• I was thinking of something different. Let me know if I'm wrong. Let's consider "riffling" two Dyke words of length m and n respectively. If, we define D(m, n) to be the function that generates the number of valid "riffles", then we could recursively define D(m, n) to be D(m, n - 1) + D(m - 1, n - 1) + ... + D(0, n - 1) with base cases D(x, 0) = D(0, x) = 1. The answer would then be D(m, n) * Cm * Cn Jun 25 at 8:25
• What about generating these for, say, n = 5 and m = 4 and then testing their numbers against your idea, comparing this with Per's idea, and then think about it again, depending on the outcome? Jun 25 at 8:40
• @ChristianStump , The answer should be D(2 * m, 2 * n) * Cm * Cn. However, strangely Per's forumla is also giving the same result which would then imply D(2 * m, 2 * n) is numerically equal to comb(2 * (m + n), 2 * m). But, how to prove it? I know how to solve recurrence relations comprising of a single variable using difference equations and generating functions but how to solve recurrence relations consisting of two variables? Jun 25 at 9:05
• Note that $C_n^2\binom{4n}{2n}=\frac{(4n)!}{n!^4(n+1)^2}$.
– YCor
Jun 25 at 9:07
• Per's answer is almost right but he forgot that there are two different parameters $n$ and $m$. Jun 25 at 13:45