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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Tuhin Mukherjee
    Commented Jun 25, 2021 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$
    – Christian Stump
    Commented Jun 25, 2021 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$
    – Tuhin Mukherjee
    Commented Jun 25, 2021 at 9:05
  • $\begingroup$ Note that $C_n^2\binom{4n}{2n}=\frac{(4n)!}{n!^4(n+1)^2}$. $\endgroup$
    – YCor
    Commented Jun 25, 2021 at 9:07
  • $\begingroup$ Per's answer is almost right but he forgot that there are two different parameters $n$ and $m$. $\endgroup$
    – Sam Hopkins
    Commented Jun 25, 2021 at 13:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .