# Choosing people based on height

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.

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}$$

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.