0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Jun 25 at 8:25
  • $\begingroup$ 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? $\endgroup$ Jun 25 at 8:40
  • $\begingroup$ @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? $\endgroup$ Jun 25 at 9:05
  • $\begingroup$ Note that $C_n^2\binom{4n}{2n}=\frac{(4n)!}{n!^4(n+1)^2}$. $\endgroup$
    – YCor
    Jun 25 at 9:07
  • $\begingroup$ Per's answer is almost right but he forgot that there are two different parameters $n$ and $m$. $\endgroup$ Jun 25 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.