1
$\begingroup$

I saw this question online, somebody told me it's the expansion of Catalan number. But I can't find the correlation. Here is the question:

There are $3n$ balls with $n$ red balls, $n$ yellow balls and $n$ blue balls. They are put in a row. Now if we pick the FIRST(from left to right in a sequence, NOT in picking time order) $k$ balls, $k$ could be $1,2,3,...,3n$ in this question, for $k=1,2,3,...,3n$, in these $k$ picked balls, red balls>=yellow balls>=blue balls. Could you please tell me how many combinations meet the requirement?

Here is a solution I found elsewhere, but the poster didn't know if this was right because he can't find the correlation between it and Catalan number as I said.

Let $x_1,x_2,x_3$ be the numbers of picked red, yellow, blue balls.

If put randomly, there are ${3n \choose 2n}*{2n \choose n}$ combinations.

If don't meet the condition of $x_1\geq x_2$ , there are ${3n \choose 2n}*{2n \choose n-1}$ combinations based on reflection principle. Similarly, don't meet the condition of $x_2\geq x_3$ , there are ${3n \choose 2n}*{2n \choose n-1}$ combinations.

And amount of combinations disobey conditions of $x_1\geq x_2$ and $x_2\geq x_3$ are ${3n \choose 2n}*{2n \choose n-2}$.

So the amount of combinations meet $x_1\geq x_2\geq x_3$ is ${3n \choose 2n}*({2n \choose n}-2*{2n \choose n-1}+{2n \choose n-2})$.

Could you find if this answer is right or not. Or if you can find another method for this question? Thank you very much!

$\endgroup$
7
  • $\begingroup$ Does it matter which red balls you pick, or only how many red balls you pick? $\endgroup$
    – saulspatz
    Commented Jul 31, 2019 at 14:59
  • $\begingroup$ you can think this way: pick balls in a row from left the right and count the colors you pick. i.e. in this row, from left to right, no matter how many balls we have picked, always red balls >= yellow balls>= blue balls. $\endgroup$
    – simplzh
    Commented Jul 31, 2019 at 15:09
  • $\begingroup$ That's the same thing you said in the body of the question; I don't understand what you mean. What does "from left to right" have to do with anything? Is picking the first red ball and the second red ball different from picking the second red ball and the third red ball, or is it not? Perhaps you should give a link to where you saw the question online. $\endgroup$
    – saulspatz
    Commented Jul 31, 2019 at 15:34
  • $\begingroup$ I mean, if you pick the first k balls, k could be 1,2,...,3n in this question, in these k balls, red balls >= yellow balls>= blue balls, for k=1,2,...,3n. $\endgroup$
    – simplzh
    Commented Jul 31, 2019 at 15:37
  • $\begingroup$ You aren't reading my questions, are you? I give up. $\endgroup$
    – saulspatz
    Commented Jul 31, 2019 at 15:38

1 Answer 1

2
$\begingroup$

It is not quite so easy to count the number of paths which violate both conditions. However, a reflection type argument is possible, and is presented in an article by Zeilberger available online here.

Here is the essence of the argument. Instead of sequences of red, yellow and blue marbles, think of discrete paths on the three dimensional grid from $(0,0,0)$ to $(n,n,n)$ whose intermediate points $(x,y,z)$ all satisfy $x\ge y\ge z$. These are "good" paths, while a path is "bad" if it at some point hits one of the planes $x=y-1$ or $y=z-1$. Given a point $(x,y,z)$, let $G(x,y,z)$ be the number of good paths from $(x,y,z)$ to $(n,n,n)$, and let $B(x,y,z)$ be the number of path paths. Obviously, letting $\binom{n}{a,b,c}=\frac{n!}{a!b!c!}$, then $$ G(0,0,0) = \binom{3n}{n,n,n}-B(0,0,0),\tag 1 $$ so the goal is to count the number of bad paths from $(0,0,0)$ to $(n,n,n)$.

The clever trick is this: you can show that

$$ B(0,0,0)+B(-2,1,1)+B(-1,-1,2)= B(-1,1,0)+B(0,-1,1)+B(-2,0,2)\tag 2 $$

To prove this, consider a bad path counted on the left hand side of the equation, i.e. starting from either $(0,0,0), (-2,1,1)$ or $(-1,-1,2)$. Reflect this portion of this path up until its first bad point, i.e. the first time it hits $x=y-1$ or $y=z-1$. The result will be a path starting from the one of the points on the right hand side of the equation, either $(-1,1,0),(0,-1,1)$ or $(-2,0,2)$. You can check this yourself, case by case; for example, if you reflect a path starting from $(0,0,0)$, the result will start from either $(-1,1,0)$ or $(0,-1,1)$, depending on which bad plane is hit first.

Furthermore, it is easy to count all of the quantities besides $B(0,0,0)$ in $(2)$, because all paths from $(-1,1,0)$ are bad, and same for the other points. Combining $(1)$ and $(2)$, you get \begin{align} G(0,0,0)=&\hspace{.5cm}\binom{3n}{n,n,n}+\binom{3n}{n-2,n+1,n+1}+\binom{3n}{n-1,n-1,n+2}\\&-\binom{3n}{n-1,n+1,n}-\binom{3n}{n,n-1,n+1}-\binom{3n}{n-2,n,n+2}.\end{align}

$\endgroup$
1
  • $\begingroup$ very good point, thanks! $\endgroup$
    – simplzh
    Commented Aug 6, 2019 at 6:28

You must log in to answer this question.

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