Understanding Ordered and Unordered Pairings in Probability Calculations

[hotvette]

Homework Statement

A football team consists of 20 offensive and 20 defensive players to be randomly paired as roommates. What is the probability there are no offensive-defensive player pairs?

Homework Equations

r-groups of n-objects outcomes = $\frac{n!}{n_1!n_2! \dots n_r!}$

The Attempt at a Solution

This is actually worked out as an example in my book (A First Course in Probability, Ross), but there is something I don't understand. It says the number of ordered pairs is $\frac{40!}{(2!)^{20}}$ and the number of un-ordered pairs is $\frac{40!}{20!(2!)^{20}}$. and the latter is used in the denominator of the probability calculation. I don't understand the context of ordered vs un-ordered and why the 2nd is used in the denominator.

It's sort of like saying there are $\frac{52!}{(13!)^4}$ ordered sets of bridge hands and $\frac{52!}{4!(13!)^4}$ un-ordered sets of bridge hands. What does that mean?

 

[LemmeThink]

Hi!
Well, let me try;) Apologies if I make a mistake!

It says the number of ordered pairs is 40!(2!)2040!(2!)20\frac{40!}{(2!)^{20}} and the number of un-ordered pairs is 40!20!(2!)2040!20!(2!)20\frac{40!}{20!(2!)^{20}}. and the latter is used in the denominator of the probability calculation.

If I understand correctly, we can view the players as, well, numbers, 1,2,3,...40. All possible arrangements of these numbers corresponds to 40! . We then make pairs of 2 adjoining numbers formed from these arrangements, let's say, the 1st and the 2nd, and so on. Now, in all the possible cases, we will have arrangements where only the numbers of a pair exchange. We want this to count as only one pair. You thus get the 2! term.
Now, however, consider the each pair as one number, like, 1st pair, 2nd pair, and so on upto 20 pairs. You can see that in all possible arrangements of the 40 players, you have cases where each of the 20 pairs is also undergoing all possible arrangements. We, however, don't want this, as our purpose is simply to form all possible pairs. We thus get a 20! term.

I hope this helps, and apologies if it doesn't.

 

[PeroK]

The starting point is to have all 40 players in an ordered list. There are 40! Ways to do this.

Then you assume 1-2 is a pair, 3-4 is a pair etc. If you are looking for ordered pairs then that means that Joe-Jeff is different from Jeff-Joe, then how many ways do you have the same 20 ordered pairs. Well that's just 20!

So the number of ordered pairs is: $\frac{40!}{20!}$

Now, if you are looking for unordered pairs, where Joe-Jeff is the same pair as Jeff-Joe, each can occur in two orders across all 20 pairs, so that's $2^{20}$ ways in total. That's the number of way that a specific set of 20 unordered can appear as a set of 20 ordered pairs.

Hence the number of unordered pairs is

$\frac{40!}{2^{20}(20!)}$

Note that my first answer appears not to agree with your book. That's a worry!

 

[PeroK]

PS try it with up to 8 players A-H. Start with 4 then 6 players.

 

[Ray Vickson]

Homework Statement

A football team consists of 20 offensive and 20 defensive players to be randomly paired as roommates. What is the probability there are no offensive-defensive player pairs?

Homework Equations

r-groups of n-objects outcomes = $\frac{n!}{n_1!n_2! \dots n_r!}$

The Attempt at a Solution

This is actually worked out as an example in my book (A First Course in Probability, Ross), but there is something I don't understand. It says the number of ordered pairs is $\frac{40!}{(2!)^{20}}$ and the number of un-ordered pairs is $\frac{40!}{20!(2!)^{20}}$. and the latter is used in the denominator of the probability calculation. I don't understand the context of ordered vs un-ordered and why the 2nd is used in the denominator.

It's sort of like saying there are $\frac{52!}{(13!)^4}$ ordered sets of bridge hands and $\frac{52!}{4!(13!)^4}$ un-ordered sets of bridge hands. What does that mean?

Suppose we have $2n$ objects that are to be formed into $n$ groups of two. An unordered pair would {1,2}, meaning that that 1 and 2 are paired together but we don't care which is written first; that is, we regard the pairs (1,2) and (2,1) to be equivalent, and so count as one pairing rather than two. An ordered pair involving objects 1 and 2 would be either (1,2) or (2,1), and presumably we have a way of telling the difference, and the difference matters to us for some reason. For counting different roommate arrangements, it is apparent that we need only look at unordered pairs.

To count the unordered pairs, start with object O1; it can be paired with $(2n-1)$ other objects. After that, we are left with $2n-2$ objects needing to be paired. Now go to the lowest-numbered object still left, and pick it next for pairing. There will be $2n-3$ objects left to be paired with it, so there are $2n-3$ such pairings. After that second pairing, we are left with $2n-4$ unpaired objects. Go to the lowest-numbered one still left, and pair it with one of the other $2n-5$ objects, etc. You can see (after some thinking about it) that any given pair such as {7,26} occurs exactly once in the list of constructed pairings. That means that the number of unordered pairings is $(2n-1)(2n-3)(2n-5) \cdots (3) (1)$. we can multiply and divide by $(2n-2)(2n-4) \cdots (2) = 2^{n-1} (n-1)!$, to conclude that the number $N_u$ of unordered pairs is
$$N_u = \frac{(2n-1)(2n-2)(2n-3)(2n-4) \cdots (2)(1)}{2^{n-1} (n-1)!} = \frac{(2n-1)!}{2^{n-1} (n-1)!}.$$
Now multiply and divide by $2n$ to conclude that
$$ N_u = \frac{(2n)!}{2^n n!}.$$

 

[hotvette]

Thanks for the explanation. I decided to try a simple example of {d1, d2, o1, o2} but can't seem to get it worked out. I can easily see there are 6 unordered pairings (d1d2, d1o1, d1o2, d2o1, d2o2, o1o2} (and 12 ordered pairs if I count (d1d2) and (d2d1) as separate pairings). In this case n=2 and we get $N_o = \frac{(2n)! }{2^n} = \frac{4!}{4} = 6$ and $N_u = \frac{(2n)! }{2^{n}n!} = \frac{4!}{8} = 3$. Clearly there aren't 3 unordered pairings.

I also tried a more complicated example of {d1, d2, d3, o1, o2, o3}. In this case I come up with 15 unordered pairings. But, using n=3, we get $N_o = \frac{(2n)! }{2^n} = \frac{6!}{8} = 90$ and $N_u = \frac{(2n)! }{2^{n}n!} = \frac{6!}{48} = 15$. So, in the simple examples I get the 'ordered' value when n=2 but the 'unordered' value when n=3.

I must be doing something wrong but can't figure out what it is.

 

[hotvette]

I've partially figured out what I was doing wrong. I was looking at how many pairs could be formed as opposed to how many groups of n-pairings. I've now worked out $N_u$ for n=2 and n=3 using trees, so that part I understand now.

Just for kicks, I decided to work out the ordered version $N_o$ for the simple case of n=2, but I come up with 12 groups of 2-pairings as opposed to 6:
$${(d_1 d_2,o_1 o_2), (d_1 d_2,o_2 o_1), (d_2 d_1,o_1 o_2), (d_2 d_1,o_2 o_1)} \\ {(d_1 o_1,d_2 o_2), (d_1 o_1,o_2 d_2), (o_1 d_1,d_2 o_2), (o_1 d_1,o_2 d_2)} \\ {(d_1 o_2,d_2 o_1), (d_1 o_2,o_1 d_2), (o_2 d_1,d_2 o_1), (o_2 d_1,o_1 d_2)}$$

What have I done wrong?