How to prove that the following conclusion is true?

77 Views Asked by At

Consider a set $\mathcal{X}$ with $m$ numbers, and take out $a, b, c, d$ numbers respectively.

The number of combinations of $a$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{a}$.

The number of combinations of $b$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{b}$.

The number of combinations of $c$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{c}$.

The number of combinations of $d$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{d}$.

If $a+b=c+d$ and $c<b<a<d$, how to prove that $C_{m}^{a}C_{m}^{b}>C_{m}^{c}C_{m}^{d}$?

1

There are 1 best solutions below

3
On BEST ANSWER

Too long for a comment.

Let's just try an example and see if it is illuminating.

Suppose $m = 12$, and that $c<b<a<d$ is, respectively, $2<3<7<8$.

So, $a=7$, $b=3$, $c=2$, $d=8$, and (as desired) $a+b=10=c+d$.

Written out combinatorially, the desired inequality to prove is:

$$\frac{12!}{7!5!} \frac{12!}{3!9!} > \frac{12!}{2!10!}\frac{12!}{4!8!}$$

The numerators are the same, so dividing both sides by $12!12!$ and then cross multiplying yields the equivalent inequality:

$$(4!8!)(2!10!) > (5!7!)(3!9!)$$

We can see this last inequality will hold by examining each of the parenthetical terms:

$4!8! > 5!7!$ because the extra term on $8!$ is an $8$, which is larger than the extra term from $5!$, which is a $5$.

If you write out a couple more examples, then perhaps you can see how this can be phrased into more general language.