Probability: Permutations and Combinations

Question

Q: Sixteen kids, 8 boys and 8 girls, are going on a train trip. Conveniently enough,

the train has precisely 8 benches and each bench seats precisely two kids. The

teacher assigns each kid at random to one of the eight benches. What is the

probability that none of the girls sits together with a boy on a bench?

I'm thinking that'd be (16C4 * 8!) / 16!. Not quite sure though, help appreciated.

Answer 1

First calculate the number of ways kids could be picked to get this result, and divide by the total number of ways kids could be picked.

The key insight in calculating the number of ways that every bench could be only boys or only girls is to recognize that for any combination of all boys and all girls benches, there are 8!*8! different orders in which the kids could be arranged on those benches, where the exclamation mark means factorial. One girl out of eight fills the first of those seats, then conditional on that, one girl out of seven can fill the second seat, etc. Which seat we call "first" or "second", is arbitrary as long as we're consistent. Then, conditional on the order that the girls are picked, there are 8 boys, so they can be picked in 8! orders that don't depend on the order that the girls are picked.

So number of ways equals

(number of ways to pick 4 benches out of 8 as girls' benches)*(number of ways to arrange kids with 4 girls' and 4 boys' benches)

which equals

(number of ways to pick 4 benches out of 8 as girls' benches)*(8!8!)

=(8^c4)*(8!8!)=(8!)/[(8-4)!*(4)!]*8!*8!=[(8*7*6*5)/(1*2*3*4)]*8!8!=70*8!*8! ways to arrange/pick kids so that 8 girls out of 16 kids are all on benches with only girls

Now we just divide this number, 70*8!*8! (use Excel if calculator overflows!) by the total number of ways to pick 16 kids, which is 16!. p=70*8!*8!/16!=.005439.

To the fourth decimal place, the answer seems to be a probability of .0054, or just over one half of one percent probability.

This is my favorite kind of problem. There are not too many words, but it requires some thought and insight.