General Question

Mariah's avatar

Why doesn't this work (combinations and permutations)?

Asked by Mariah (18929 points ) September 24th, 2012

There is a group of 13 people and you are to choose 10 of them (order doesn’t matter) – trivially, this is 13C10 = 286.

Now say 3 of the people are women and you are to choose a team that includes at least one woman. This is equal to the total number of groups minus the one grouping that is only men, 285.

Another way I thought about the problem doesn’t yield the right answer even though it seems to make sense. It goes as follows: choose one woman to include on the team – 3C1 – then choose any grouping of the remaining people – 12C9. Multiply and get 660, which is obviously wrong because it’s larger than the number of possible teams even when you place no restrictions on your choice-making parameters.

Why is this method wrong?

Observing members: 0 Composing members: 0

6 Answers

CWOTUS's avatar

It seems to me that in the multiplication you’re attempting that you’re double-counting some of the groups, aren’t you? I’m having a hard time visualizing this, but I went to Wolfram Alpha and determined (after I verified that 13C10 = 286) that:

12C9 = 220
11C9 = 55 (after the first set of all choices for 1 of the 3 women)
10C9 = 10 (the remaining choices after the first two women’s choices are counted)

The sum of these permutations is the same 285 that you expected.

Mariah's avatar

I too think the multiplication wasn’t appropriate but I can’t quite put my finger on why.

PhiNotPi's avatar

Here is the reason that your second method is wrong- because it distinguishes between identical groups picked in a different order.

Say persons 1,2,3 are female, and everyone else (4–13) are male.

Let’s say that the group picked was {1,2,3,4,5,6,7,8,9,10}.

If you followed the second method, you could have done one of the following:
Pick woman 1 and pick other people {2,3,4,5,6,7,8,9,10}
Pick woman 2 and pick other people {1,3,4,5,6,7,8,9,10}
Pick woman 3 and pick other people {1,2,4,5,6,7,8,9,10}

Each of these ways are counted individually by the second method, but are actually the same.

Mariah's avatar

@PhiNotPi Aha! Thanks.

LostInParadise's avatar

A second way of arriving at the answer is to reason that there must be 1, 2 or 3 women.
The number of ways of having exactly 1 woman is 3C1 * 10C9
The number of ways of having exactly 2 women is 3C2 * 10C8
The number of ways of having all 3 women is 3C3 * 10C7.
Adding together gives 3 * 10 + 3 * 45 + 120 = 285
That is probably how I would have solved, not seeing your shortcut.

prasad's avatar

It’s the difference between “or” and “and”, and making it exhaustive.

You are to find number of ways that the team can be chosen with at least one woman. Now, “at least” implies you can choose more than one (one woman or two women or three women). In simple words, it will be like:

Number of ways = (1 woman and 9 men) or (2 women and 8 men) or (3 women and 7 men)
...consider all possibilities here.

Remember, “and” will be replaced by multiplication and “or” will be replaced by addition.

So, the answer becomes:

Number of ways = (3C1 * 10C9) + (3C2 * 10C8) + (3C3 * 10C7) = 30 + 135 + 120 = 285.

Another way, though you already have it, is:

Number of ways = Total number of ways that a team can be formed – All team consists of men
=(13C10) – (10C10) = 286 – 1 = 285.

We have, in total, 13 people of which 10 are men and 3 are women.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther