Choosing people based on height

Question

How many ways are there to pick a group of $n$ people from $100$ people (each of a different height) and then pick a second group of $m$ other people such that all people in the first group are taller than the people in the second group?

My attempt:

Let us select $m+n$ people among $100$. Arranging them in ascending order of height, we need to separate them into groups of $m$ and $n$ such that the group with $n$ is taller. There is only one way to do this. So answer is $$^{100}C_{m+n}$$

But the answer is given as $$\sum_{r=0}^{100-m} {}^{m+r}C_m \cdot {}^{100-m-r} \space C_n$$

I don't understand what I did wrong and how the given answer is derived.

Answer 1

You are correct. $ \displaystyle {100 \choose m+n} ~$ does count number of ways to make two groups where $n$ people in the first group are taller than $m$ people in the second group.

First of all, the upper limit in the sum is incorrect. It should be $\displaystyle \sum_{r=0}^{100-m-n} {m+r \choose m} {100-m-r \choose n}$

The only explanation for the given expression is that it is trying to choose $m$ people from $(m+r)$ shortest people and then $n$ people from the remaining people. But ${m+r - 1 \choose m}$ is a subset of ${m+r \choose m}$ which leads to duplicates. So the given answer is definitely incorrect for the given question. The correct expression, without duplicates, would be

$ \displaystyle \sum_{r=0}^{100-m-n} {m+r-1 \choose m-1} {100-m-r \choose n}$

So you choose $m$ from $m+r$ shortest people but you always choose the tallest person among them, that is $(m +r)^{\text{th}}$ person, ensuring you have unique groupings for every $r$. But of course nothing beats the simple solution of $\displaystyle {100 \choose m + n}$

Answer 2

Your answer is correct, and the given answer involves multiple overcounting.

Suppose $10$ shorter group and $5$ taller group are to be selected.

The given answer amounts to $\binom{10}{10}\binom{90}{5} + \binom{11}{10} \binom{89}{5} + ....\;$

ie select the $10$ shortest and $5$ taller from the remaining $90$
plus select $10$ from the $11$ shortest and $5$ taller from the remaining $89 .....\;$ and so on

But the $10$ shorter in the second case could well be the ten shortest hence multiple overcounting is there in the given answer.