Picking groups x and y from 100 people.?

Question

How many ways are there to pick a group of x people from 100 people (each person is a different height), and then pick a second group of y (different) people so that everyone in the first group is taller than everyone in the second group?

All 100 people do not have to be picked. So if the 100 people are numbered from shortest to tallest, you can have group x with Number 3, and group y with Number 1 and/or 2.

Answer 1

OK. I got it. he he he :)

First things first: given N people, how many groups can be formed? Well, every person can either be or not be a member of a group, so the answer is 2^N. If however we exclude the empty group, the answer becomes 2^N - 1.

Now, let's suppose the people are lined up from tallest to shortest. Let's call the last guy in the "taller" group the "divider".

Supose the divider is in position 1. Then, we have
(2^1 - 1) * (2^99 - 1) groups.

position 2: (2^2 - 1) * (2^98 - 1) groups
position 3: (2^3 - 1) * (2^97 - 1) groups
...
position k: (2^k - 1) * (2^(100-k) - 1) groups.

So we need to some these things up, for divider positions from 1 to 99.

(2^k - 1) * (2^(100-k) - 1) = 2^100 - 2^k - 2^(100-k) + 1

so what we're looking for is

sigma (k from 1 to 99) of (2^100 - 2^k - 2^(100-k) + 1) =
99 * 2^100 + 99 - sigma (k from 1 to 99) of (2^k + 2^(100-k)) =
99 * 2^100 + 99 - sigma (k from 1 to 99) of (2^k) - sigma (k from 1 to 99) of (2^(100-k)) = (since both sigmas are the same)

99 * 2^100 + 99 - 2 * sigma (k from 1 to 99) of (2^k) =
99 * 2^100 + 99 - 2* (2^100-2) =
97 * 2^100 + 103

if we allowed for empty groups, the answer would be much prettier: 100 * 2^100

Answer 2

If x + y >100, then there are zero ways.

If x + y =100, then there is 1 way.

Now, if x + y < 100 then number is harder to calculate. Line the people in order from tallest to shortest. Somewhere from the xth tallest to the yth shortest (inclusive) pick a person to be the 'divider'.

This divider partitions the 100 people into two groups of sizes n1>x and n2>y. You can then use the hypergeometric distribution to calculate the ways to choose x of n1 and y of n2.

lastly, since the divider person could have been any one of 100 -x -y people, you will need to add the totals from 100 - x -y separate hypergeometric dist. calcs.

Answer 3

There are 99*99*99 ways.
You do the math.