a prob ques

[bitzz]

question:

a football team consists of 20 offensive and 20 defensive players. the players are to be paired in grps of 2 for the purpose of determining roomates. if the pairing is done at random, what is the prob that there are no offensive-defensive roommate pairs?

the ans goes like this: the denominator of the prob is (40)!/((2^20)(20)!) and the numerator is ((20)!/((2^10)(10)!))^2.

why is there the (20)! at the bottom of the denominator and (10)! at the bottom of the numerator.

the book kinda explained that its 'cos its unordered pair, but i don't understand why have to divide by (20)! & (10)!?

[jemidiah]

The denominator should be the total number of possible roommate states, that is, the total number of (unique) 20-pairs. Here's my reasoning through how we choose those matchings of 20-pairs.

Equation: (40)!/((2^20)(20)!)

Choose the first through 40th people and make every two a pair, giving you 40! matchings. This over counts horribly, since choosing person W, X, Y, and then Z is the same as choosing Z, Y, X, W for instance. Get rid of duplicates by dividing off the number of players in each equivalence class. First you can have any of the twenty pairs inverted [this is getting rid of the case when Z+Y != Y+Z]. You can do 2^20 different sets of inversions (for each pair, pick whether or not it's inverted = 20 choices between two equally likely things). But that doesn't get rid of all of the duplicates, since you could still pick [W+X, Y+Z] and [Y+Z, W+X] and they'll be counted differently. This is where the 20! comes from.

You can order 20 objects (pairs) in any of 20! ways, by first choosing the first object from 20 choices, then the next from 19, etc. So, we have 20! equivalent orderings of 20 pairs, but right now they're each being counted as different matchings. So, divide by 20!. Thinking about it backwards, for each unique unordered matching, you could order the pairs in any of 20! ways. Since you're counting each ordered matching uniquely, to get the number of unordered matchings you have to divide by 20!.

These are the only imposed orders I can think of (you could probably reason through that they're all of them), so we get (40)!/((2^20)*20!) distinct matchings, explaining everything in the equation you gave.


I suspect the numerator is a similar trick, that you've imposed an order on the pairs you choose, but haven't reasoned through it. If you get stuck on it I'll think about it for a while but combinatorics isn't my forte.

[Logophobic]

Not just similar, it's exactly the same. It counts the number of unique pairings of 20 players, squared (pairings of offense-only times those of defense-only).

Looking at it again, I notice that the powers of 2 cancel out, leaving 20!³/(40! * 10!²)

[wy125]

I'm not an expert or anything but I'm having a hard time understanding that solution also. That was from a book? Could you post a bit more of the solution from the book?

This is how I see it:

The probability of getting no offensive defensive roommate pairs is given by the number of unordered offense-only pairs + the number of unordered defense-only pairs divided by the total number of pairs possible. I think this should be:

Number of offensive-only pairs = nCr(20,2) = 20!/[(20-2)!*2!] = 20!/(18! * 2)
Number of defensive-only pairs = offensive pairs = nCr(20,2) = 20!/(18! * 2)
Total number of pairs = nCr(40, 2) = 40!/[(40-2)!*2!] = 40!/(38! * 2)

This reduces to: 19/39

I know this is nothing like that answer you've found and it doesn't answer your question but I am curious now how they got the result you posted. If you get a chance can you post more of an explanation from the text?

[Logophobic]

What you have calculated is the probability that a single, randomly chosen pair of players is either O-O or D-D. The question asked for the probability that, with all players paired, all of those pairs are either O-O or D-D.

[wy125]

haha I missed that in the original post. Now the powers make sense

[jemidiah]

The factors of 2 should cancel out (combinatorially) because we can compute the same probability whether or not we count inverted pairs as being unique. I love that combinatorial proofs assign meaning to algebra like this.