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!
Best Answer
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
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}