6
$\begingroup$

A combinatorics question goes like this :-

There are 10 couples who wish to play mixed doubles tennis, without there being a couple in the court, i.e., there cannot be a husband of a wife, or vice versa either in the same team or opposite team. How many ways are there to play the match?

I did this like:- We can select the first wife in 10 ways, the second wife in 9 ways. Now there cannot be 2 husbands of these wives. So for selecting the husbands there are 8 X 7 ways. Total no.of ways = 10 X 9 X 8 X 7 = 5040. But the answer is 2520 = 1/2 (5040). Where am I wrong? Thank You.

$\endgroup$
16
$\begingroup$

You have to divide your result by $2$ because the match Joe and Sally versus Bob and Emma is the same match as Bob and Emma versus Joe and Sally.

$\endgroup$
  • $\begingroup$ sir but where am I counting the matches twice? $\endgroup$ – Ram Keswani Nov 2 '17 at 9:35
  • 9
    $\begingroup$ @RamKeswani You only count the number of possible 4-tuples $(M_1,W_1, M_2, W_2)$ that can appear on the court, and then say that $M_1,W_1$ are playing against $M_2,W_2$. However, this way, you count both the $4$-tuple $(M_1,W_1, M_2,W_2)$ and the $4$-tuple $(M_2,W_2,M_1,W_1)$, but they both represent the same match. $\endgroup$ – 5xum Nov 2 '17 at 9:37
  • $\begingroup$ @RamKeswani You're double-counting at the very beginning, when you say there are $10$ x $9 = 90$ ways to pick the two wives. There are 2 ways to pick each pair of wives (you can pick either wife first), so $90$ ways of picking them corresponds to $45$ pairs. $\endgroup$ – MartianInvader Nov 2 '17 at 18:43
6
$\begingroup$

$2$ men are selected from $10$ men in $\binom {10}{2} $ ways. Since, no husband and wife should be in the same game, 2 women from the remaining $8$ can be chosen in $\binom {8}{2} $ ways. There are 2 ways of choosing a team - $(M_1, W_1)$ and $(M_1,W_2) $.

Total number of ways $= 45 × 28 × 2 = 2520$.

$\endgroup$
  • $\begingroup$ right sir but what I am asking is where I am wrong. $\endgroup$ – Ram Keswani Nov 2 '17 at 9:30
  • $\begingroup$ @RamKeswani You are wrong because you count each match twice. $\endgroup$ – 5xum Nov 2 '17 at 9:32
  • 3
    $\begingroup$ @RamKeswani First Wife- $W_1$ Second Wife - $W_2$ Man 1 - $M_1$ Man 2 - $M_2$ The match between $(M_1, W_1) $ and $(M_2,W_2) $ is the same as that between $(M_2,W_2) $ and $(M_1,W_1) $. This is double counting. Hence divide by 2. $\endgroup$ – Rohan Nov 2 '17 at 9:34
  • $\begingroup$ @5xum yes sir I saw your answer, i was just telling Rohan that I wanted to know where I was wrong and not the answer. $\endgroup$ – Ram Keswani Nov 2 '17 at 9:34
  • $\begingroup$ @RamKeswani Hope you have understood. $\endgroup$ – Rohan Nov 2 '17 at 9:35
6
$\begingroup$

You are confusing the difference between an order of events (e.g picking) and making an unordered selection (e.g choosing).

When you say there are $10 \times 9 = 90$ ways to select the wives, you get the wives in a certain order. You're saying that W1W2 is not the same as W2W1. With the remaining husbands, again $8 \times 7 = 56$ ways is suggesting order matters.

Furthermore, you haven't made teams by picking these people in order. If you chose one of your selected people to go first and pick their partner, there are $4 \times 2 = 8$ ways for the teams to be picked which you didn't account for. If we don't care about order, there are only 2 ways to form a team from 2 wives and 2 husbands.

The problem here is, the order of picking doesn't matter. The question you've answered is 'how many ways can I pick two wives and two husbands, in that order, none of which are married to each other'. The order of selection doesn't affect who is playing and whether the rule of a couple being on the court is violated.

Often in combinatronics you will seen "n choose k" using the notation $\binom {10}{2} $, e.g. from 10 choose 2 = 45 possibilities (not $10 \times 9 = 90$). When choosing, order does not matter.

So, correcting your answer, you have 2x too many wives and 2x too many husband possibilities (as W1W2 is the same as W2W1), so you need to divide your answer by 4. Then you need to multiply by 2 to account for the step you missed: choosing a team from the results (any given wive or husband only has two people to choose from to form a team + the remainders being forced into a team = 2 possibilities from 2 wives and 2 husbands).

Alternatively, you can multiply out the right numbers: $\binom {10}{2} \cdot \binom {8}{2} \cdot 2 = 45 \times 28 \times 2 = 2520$

$\endgroup$
2
$\begingroup$

You have double counted at the very first step

Let the two wives chosen be Alice and Betty.

Now the court has a left side and a right side, so when you write $10 \times 9$ for selecting them,

You are, courtwise, including Alice | Betty and Betty | Alice,
but it doesn't matter whether Alice is on the left side or right side.

$\endgroup$
1
$\begingroup$

Another way to solve the problem in 3 steps:

(1) Let family names of couples be A B C D ... There will be 4 family names present in a game, so we have (10 choose 4) = 210 combinations.

(2) Assume couples A B C D are playing a game. There are (4 choose 2) = 6 ways to pick two husbands out of A B C D. Once we pick two husbands (say from couples A B), the remaining two couples (C D) provide wifes for the game.

(3) Now assume husbands A B and wifes C D playing a game. There are 2 possible such games: AC|BD or AD|BC, where | means the tennis net.

Altogether we have 210*6*2=2520 possible games.

$\endgroup$
0
$\begingroup$

In combinatorics they often use these notations:

  • $n!$
    = $n$ factorial = In how many ways can I order $n$ elements
    $10! = 10 \times 9 \times 8 \times \dots \times 1$
  • $n \choose k$
    = $n$ choose $k$ = How many groups of $k$ elements can one pick from a group of $n$ elements, irrespective of order.
    This corresponds to picking an ordering for the entire group and then selecting the first $k$ elements as your resulting group. This way you count the same group multiple times though. This symmetry is addressed by dividing by the number of combinations possible in each subgroup. This is where the formula comes from, but this notion of removing the symmetry is important for your problem as well.
    = $\frac{n!}{k! \times (n-k)!}$

So what are you doing right?

Selecting 2 wives: $10 \times 9 = \frac{10!}{8!} = \frac{10!}{(10-2)!}$
Selecting 2 husbands: $8 \times 7 = \frac{8!}{6!} = \frac{8!}{(8-2)!}$

This gives you $5040$ possible combinations.

So what are you doing wrong?

Looking at the formulas there is something missing: the term used to account for the symmetry. Knowing this, intuitively the formulas should be as follows:

Selecting 2 wives: ${10 \choose 2} = \frac{10!}{(10-2)! \boldsymbol{\times 2!}} = \frac{10 \times 9}{2}$
Selecting 2 husbands: ${8 \choose 2} = \frac{8!}{(8-2)! \boldsymbol{\times 2!}} = \frac{8 \times 7}{2}$

Leading to $1260$ possible combinations. But this is wrong as well because we cannot blindly follow the formulas without interpreting them. If we do that we see that the order of the husbands is indeed important.

The choice for the wives determines the teams, their order does not matter because team 1 playing against team 2 is the same as team 2 playing against team 1. Afterwards you select for each team a single husband to join. The correct formulas would thus be:

Selecting 2 wives: ${10 \choose 2} = \frac{10 \times 9}{2}$
Selecting 2 husbands: ${8 \choose 1}{7 \choose 1} = 8 \times 7$

This leads to the correct answer of $2520$ combinations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.