5

On my example final exam, we are given the following problem:

 How many ways can we pick seven balls of three colors red, blue, yellow given
 also that the number of red balls must be strictly greater than blue and
 blue strictly greater than yellow?

The solution I used (and was given) was a brute force counting. In particular, fix the number of red balls for $0, 1, \dots, 7$ and see how many viable cases we procure each time.

However, I wanted to try and find a more clever way to do it, but couldn't. Is there a better/general way to do this problem when the numbers get larger?

If possible, it would be even better if we solve the following more generalized form:

$$x_1 + \dots + x_n = c, x_1 > \dots > x_n \geq 0$$

MT_
  • 19,603
  • 9
  • 40
  • 81

1 Answers1

0

For the case $n = 3$, since $x_2 > x_3 \geq 0 \Rightarrow x_2 \geq x_3+1 \Rightarrow x_2=x_3+1+r, r \geq 0$, and similarly, $x_1 > x_2 \Rightarrow x_1 \geq x_2+1 \Rightarrow x_1=x_2+1+s = (x_3+1+r)+1+s = x_3+2+r+s$. Substituting these into the equation: $x_3+2+r+s + x_3 + 1 + r + x_3 = c \Rightarrow 3x_3+2r+s = c-3$. From this we can divide into cases with $x_3 = 0, 1,2,...,\lfloor \frac{c-3}{3}\rfloor$. This can generalize to $n$.

DeepSea
  • 77,651