# Understanding when to use product rule and when to use sum rule?

Suppose there are $n$ couples in a party. What is the way of choosing a man and a woman who are not a couple.

I can choose a woman in $n$ ways ($E_1$), and I am left with $n-1$ choices for a man not her husband ($E_2$). Now, I cannot decide if I should use the sum rule or the product rule, i.e are the total possibilities $2n-1$ or $n^2-n$. $E_1$ and $E_2$ do not seem to be independent, as the event E_1 automatically determines the set of $E_2$. The sum rule sounds possible, as $E_1$ and $E_2$ cannot occur simultaneously (because I will have to choose a woman first and then choose a man from the remaining set).

I am having trouble when to use sum and product rules in general.

-
Perhaps you'd benefit from reviewing the rule of sum and the rule of product. –  Stijn May 11 '11 at 17:16

The sum rule would tell you how many ways to pick either a woman, or a man who is not her husband; that doesn't really make sense at all (how can you only pick "a man who is not her husband"?), so the sum rule cannot be applicable here.

You can also argue by overcounting and then compensating, as follows: there are $n^2$ ways to pick a man and a woman ($n$ ways to pick the woman, $n$ ways to pick the man; you want to pick both, so you multiply them). But of these $n^2$ ways to pick a man and a woman, $n$ of them pair up a woman with her husband. So $n$ of the $n^2$ selection are "no good", so we must take them off. This gives a total of $n^2-n$ possible ways of picking the couple.

-
I think the main problem with combinatorics is that the problems can be worded, and ordinary words bring a mixture of linguistic interpretations which in my use of ordinary language are quiet amorphous. After doing some research, your exposition here was most helpful, using your definitions this answer makes perfect sense. +1 and thanks. –  kuch nahi May 11 '11 at 18:13

Perhaps you should think of it this way. For every choice of woman, there are $n-1$ ways of choosing the man. This is analogous to the following problem. There are $n$ women in a group. Every one of these has $n-1$ children. How many children altogether?

Or else imagine listing the possibilities. Using the obvious notation, they are

$W_1M_2$, $W_1M_3$, $W_1M_4$, and so on until $W_1M_n$

Then come

$W_2M_1$, $W_2M_3$, $W_2M_4$, and so on until $W_2M_n$

Continue, until we get to

$W_nM_1$, $W_nM_2$, and so on until $W_nM_{n-1}$

Each "row" has $n-1$ entries, and there are $n$ rows, for a total of $n(n-1)$.

Or else draw a "tree diagram."

-

As Arturo showed, you can use both rules depending:

• choose the woman ($n$ ways), then choose the man ($n-1$ ways) this is a sequence so you multiply to get $n(n-1)$. They are independent because you removed the dependency by subtracting 1.
• choose all possible pairs $n^2$ (using the product rule), then exclude the pairs not wanted $n$, or $n^2 - n$. The latter is just an inverse of the rule of sum, where the total possible pairs is the sum of the given couples $n$ plus all the other ways of making the couples (exercise for the reader...or rather the next problem in the sequence).
-
This is a great answer. +1 –  kuch nahi May 11 '11 at 18:17