Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many ways are there first to pick a subset of $r$ people from $50$ people (each of a different height), and next to pick a second subset of $s$ people such that everyone in the first subset is shorter than everyone in the second subset.

My initial solution was that I could somehow split the people up into two groups, arranged from shortest to tallest, then that way I would be guaranteed that the first subset chosen would be shorter than the second subset... But that's not the right answer.

I believe the correction solution is $\binom{50}{r+s}$, but I don't understand how this is two subsets nor how it would guarantee the height requirement.

Is it possible that my solution could somehow work?

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

Yes, just pick any $r+s$ people. There are $\binom{n}{r+s}$ ways to do this. Now we must put the shortest $r$ people in this group of $+s$ into the first set. There is only $1$ way to do this.

If you try to pick the group of $r$ "shorties" first, then there will be varying numbers of ways to pick the group of "tallies," depending on how tall the tallest shortie is. So the counting will be substantially more complicated.

share|improve this answer
    
But doing what you say in the first paragraph doesn't make sense to me because it seems like you're cheating almost. Instead of first picking $r$ people and then $s$ as the problem states explicitly, you pick $r+s$ people and then it's like you say, "Oh, well why don't I just pick the the $r$ shortest from the $r+s$ and pretend I picked them first." When in reality you didn't actually pick those $r$ people first, you picked the $r+s$ people all together. –  AlanH Jan 23 '13 at 5:43
    
If we always insist on counting a set the way it is described, we will often have a very hard time counting. Simple example: you want to count objects with certain property. It can be much easier to count the objects that don't have the property. Are you going to argue that's cheating? Point here is we have an easy way of counting. –  André Nicolas Jan 23 '13 at 12:35
    
So just to make sure I understand this correctly. Say $r=5$ and $s=3$. You pick the $8$ from the $50$, and then you take the five shortest from the $8$. Thanks for your help! –  AlanH Jan 23 '13 at 17:01
1  
Yes, exactly. And once you have picked the $8$, there is no freedom of action left, we must pick the $5$ shortest. –  André Nicolas Jan 23 '13 at 17:11
add comment

Choose any group of people of size r+s. Take the r shortest people in this group. There is only one way of choosing these people(as everyone has different heights).The remaining people form the 2nd set. So the number of ways of forming these sets is the same as the no. of ways of choosing a group of size r+s=50Cr+s

share|improve this answer
add comment

Call the first subset $A$ and the second one $B$. Notice that $C = A \cup B$ is an arbitrary subset with $r+s$ elements, and that your conditions imply that, given $C$, you can reconstruct $A$ and $B$ uniquely.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.