# Probability/Combinatorics Example Question

Hi I'm doing an example problem from Sheldon Ross and am confused. I got the first part of the question so I only listed the 2nd part:

Question: A football team consists of 20 offensive and 20 defensive players. The players are to be paired in groups of 2 for the purpose of determining roommates. What is the probability that there are 2i offensive–defensive roommate pairs, i = 1,2,...,10?

20 Offensive (O), 20 Defensive (D) ==> 40 people total and 20 pairs

The question asks for the probability of 2i OD pairs. If we have 2i OD pairs, then we have $(20-2i)$ OO and DD pairs. So I think the solution will be of form:

$\frac{(\mbox{total OD pair combinations}) \cdot (\mbox{total OO Comb)(total DD comb})}{\mbox{total unordered pair combinations} }$

Total unordered pair combinations = $\frac{1}{20!}\binom{40}{2,...,2}=\frac{40!}{20!(2!)^{20}}$

Total OD pair combinations = $\binom{20}{2i}\binom{20}{2i}(2i!)$
This is because out of 20 O's and 20 D's, we pick 2i from each to get 2i OD pairs. My first question is why do we multiply by $[(2i)!]$ ? Doesn't this give us a repeated count? I mean, assume we have 20 O's and 20 D's, then $O_1D_3$ pair is equivalent to $D_3O_1$. Aren't we over counting by multiplying by $[(2i)!]$?? Because our denomenator is the unordered pair of combinations it seems to conflict to me...

The next part is where I really get confused. Now we calculate combinations of $(20-2i)$ pairs. So I assume we have to use the binomial theorem again:

$\binom{(20-2i)!}{???}^2$ Apparently, the ???= $(10-i)!$.
Can someone please explain this step by step? Am I correct to say that $(20-2i)$ = [the number of OO or DD pairs remaining?] Maybe I'm confused on what i means? If they say we have 2i OD pairs that means we have 2i O's and 2i D's right? I can't put these pieces together.

Soln: $\cfrac{\binom{20}{2i}^2(2i)! \left[ \cfrac{(20-2i)!}{2^{10-i}(10-i)!} \right]^2} {\cfrac{40!}{2^{20}20! }} i=0,1,...,10\tag{$\diamondsuit$}$

I don't know how to adjust latex size so I apologize if it comes out small.

-
If you put $P=\cfrac{...$ instead of $P=\frac{...$, you'll get a nicer looking fraction. –  Cameron Buie Apr 26 '13 at 22:32
If there are $(2i)$ offensive-defensive pairs, then there are $\binom{20}{2i}^2$ ways of selecting 4i players involved (2i offensive and 2i defensive). These players can be paired in $(2i)!$. So that's why there is in the numerator $\binom{20}{2i}^2\cdot (2i)!$. But why are we paying attention to ordering for the OD pairs when this is calculated? For instance $O_1D_5 = D_5O_1$. All other terms have divided by the number of permutations of pairs. There's a $2^{10-i}$ and $2^{20}$. Can anyone please explain this to me? –  user1527227 May 1 '13 at 19:19

To count the number of possible ways to make $2i$ DO-pairs, we need to count the number of ways to choose the $2i$ offensive players (each of whom will be paired with a defensive player), the number of ways to choose $2i$ defensive players, and the number of ways to match two such selections up in a one-to-one fashion. There are $(2i)!$ ways to accomplish this last. But why? We may as well match them up as follows:

There are $2i$ ways to pair off the offensive player (in the group of $2i$) with the smallest jersey number, there are $2i-1$ ways left to pair off the offensive player with the second-smallest jersey number, and so on, until there is only one choice left for the offensive player with the highest jersey number.

(We won't be able to match up the rest of the players in the same way. Why does it work here and not there?) Hence, there are $$\binom{20}{2i}^2(2i)!\tag{\clubsuit}$$ different collections of $2i$ DO-pairs.

Now, we need to see how many ways we can pair off the $20-2i$ remaining offensive players, and how many ways we can pair off the remaining defensive players (these numbers will of course be equal). The number of ordered pair combinations of $20-2i$ players is $$\frac{(20-2i)!}{(2!)^{10-i}}=\frac{(20-2i)!}{2^{10-i}}=\frac{2^i(20-2i)!}{2^{10}},$$ and the number of unordered pair combinations is $$\frac{2^i(20-2i)!}{2^{10}(10-i)!}.$$ The number of ways to pair off all the remaining offensive players with each other and all the remaining defensive players with each other is therefore $$\left(\frac{2^i(20-2i)!}{2^{10}(10-i)!}\right)^2.\tag{\heartsuit}$$

-
When it says there are $2i$ defensive-offensive pairs, then there are a total of 2i offensive players and 2i defense players in the pairs right? –  user1527227 Apr 27 '13 at 1:37
That is correct. –  Cameron Buie Apr 27 '13 at 1:40
Suppose we have men $A,B,C$ and women $D,E,F$, and we want to put them all in man-woman pairs. We can choose the men being grouped with women in $\binom33=1$ way, and likewise with the women. There are then $3!=6$ ways to pair them together: (1) $AD,BE,CF$; (2) $AD,BF,CE$; (3) $AE,BD,CF$; (4) $AE,BF,CD$; (5) $AF,BD,CE$; (6) $AF,BE,CD$. Thus, the number of ways we can make unordered pairs of men and women is $$\binom33^2\cdot 3!.$$ (cont'd) –  Cameron Buie May 1 '13 at 19:45
(cont'd) If on the other hand there is some order ascribed to the list (say if each pair will be given some distinct task), then this isn't all, since swapping the order of the pairs in a list will give you a list that means something different. For example, let's consider the first list from above. There will be $3!=6$ different ways to list those pairs: (1i) $AD,BE,CF$; (1ii) $AD,CF,BE$; (1iii) $BE,AD,CF$; (1iv) $BE,CF,AD$; (1v) $CF,AD,BE$; (1vi) $CF,BE,AD$. There are $6$ ways to rearrange any list of 3, so there are $$\binom33^2\cdot(3!)^2$$ ways to make an ordered list of pairs. (cont'd) –  Cameron Buie May 1 '13 at 19:55
(cont'd) Let's put it another way, though, just for clarity. There are $$\binom{20}{2i}\cdot(2i)!$$ ways to choose $2i$ of the offensive players and put them in a line, and there are likewise that many ways to choose $2i$ defensive players and line them up. Now let's match them up by just putting the first player in one line with the first in the other, and so on down the lines. There are then $$\left(\binom{20}{2i}\cdot(2i)!\right)^2$$ ways to do this. However, we're overcounting, because the order in which the pairs were chosen doesn't matter. (cont'd) –  Cameron Buie May 1 '13 at 20:01

Imagine that there are $20$ rooms, labelled Room 1, Room 2, and so on. We can pick the occupants of these rooms in $\frac{40!}{2^{20}}$ equally likely ways. This number will be our denominator.

If there are $2i$ OD pairs, then there are $10-i$ OO pairs and $10-i$ DD pairs.

We can pick the rooms that will hold the OD pairs in $\binom{20}{2i}$ ways. For each such way, we can pick the rooms that will hold the OO pairs in $\binom{20-2i}{10-i}$ ways. By simplifying, we find that the number of ways to classify the rooms is $\frac{20!}{(2i)!(10-i)!(10-i)!}$.

Now we fill the rooms. The first OD room can be filled in $20^2$ ways. For each such way, the next OD room can be filled in $19^2$ ways, and so on, for a total of $(20)^2(19)^2\cdots (20-i+1)^2$ ways. We may prefer to write this as $\frac{(20)^2}{((20-i)!)^2}$.

Now we fill the $10-i$ OO rooms. The number of ways to do this is $\frac{(20-2i)!}{2^{10-i}}$. And for each of these, there are $\frac{(20-2i)!}{2^{10-i}}$ ways to fill the DD rooms.

It follows that the number of favourables is $$\frac{20!}{(2i)!(10-i)!(10-i)!}\frac{(20!)^2}{((20-i)!)^2}\frac{((20-2i)!)^2}{2^{20-2i}}.$$

-
Sorry Andre, I corrected the answer from the book. I wrote it incorrectly as you stated. –  user1527227 May 1 '13 at 17:35
Thanks for your help. Can you explain the source of the $(2i)!$ in the numerator of my solution? Is it correct to say that $\binom{20}{2i}\binom{20}{2i}$ gives the number of combinations of unordered pairs, but by multiplying by $(2i)!$ we are getting the number of ordered pairs? –  user1527227 May 1 '13 at 17:39
If that's the case aren't we over counting? In all of the other cases we divided by the number of permutations to get rid of the ordering but in this case we multiplied? In the 3rd term of numerator, we divided by $2^{10-i}$ and in the denomenator we divided by $2^{20}$ to get rid of pair ordering. Can someone please explain? –  user1527227 May 1 '13 at 17:47
I am not getting rid pf the permutations, except for the permutations of paired people. The only important thing is to count the same thing in numerator and denominator. The division by $2^{10-i}$ (twice) is because we want to count the number of pairs. –  André Nicolas May 1 '13 at 18:17