Question on combinatorics

[Gmat Pro]

Hi Ron,

I have a general question on combinations, where the slot method and the nCr formula yield different results. Can you tell me the correct answer and what is flawed in either approach?

Q. A manager has to choose a group of 5 people out of 10 (A - J) such that 2 people (A and B) are never together. How many such groups are possible?

There are 2 ways to solve this:

1) Using the combinations formula nCr

Total no. of groups possible for choosing 5 out of 10 people = 10C5
No. of groups in which A and B are always included = 8C3

Therefore, Number of groups where A and B are never together = Total no. of groups possible - Groups where A and B are always included
= 10C5 - 8C3
= 196 groups


2) Using the slot method

There are 3 ways in which A and B can never be together in a group:

a) A is selected, but B is not
b) B is selected, but A is not
c) Both A and B are not selected in the group

a) A is selected, but B is not
1 8 7 6 5

-First slot is A
-Second slot cannot be B and A is already chosen out of the 10, so 8 possibilities
-Third slot - 7 possibilities, 4th: 6, 5th: 5
-Order does not matter and there are 5 positions, so divide by 5!

Total no of groups which contain A but not B =( 1*8*7*6*5)/5! = 14

b) B is selected, but A is not

Similar to a) Replace A by B

1 8 7 6 5

No. of groups which contain B but not A =( 1*8*7*6*5)/5! = 14

c) Both A and B are not selected in the group

8 7 6 5 4

-First slot cannot be A or B, same holds for the remaining slots
-Order does not matter and there are 5 positions, so divide by 5!

No. of groups which contain neither A nor B = (8*7*6*5*4)/5! = 56

Combining a), b) and c),

Total no. of groups where A and B are not together = a) + b) + c) = 14+14+56 = 84 groups

Please help!

[RonPurewal]

your second approach is faulty.

you can't divide by the 5! in those examples, because you haven't actually created 5 interchangeable positions. you've defined the first position as A, which is distinct from all the others. so, not interchangeable.

[RonPurewal]

the easiest way to see what's wrong is to frame the situation in terms of just "picking" the REST of the choices, after A and/or B.

for instance, consider your case #1 (A is selected, B is not).
just say that A has been already selected; obviously there's only 1 way to do that.
now let's just say that A is already up there on stage, and your problem is to pick 4 people to go with A (where B isn't one of them).
that's just (8•7•6•5) / 4!
so, that's the correct number for your case #1.

if you consider A as another 'selection' then it's just (1)(8•7•6•5) / (1!•4!).

same with the others.

[Gmat Pro]

Dear Ron,

Sorry for the late reply, I couldn't read your reply as I was out on surgery.

I tried out your method on a selection of 3 out of 4 objects (A,B,C,D) and it works beautifully.

There are totally 4 groups of 3 members possible: ABC, BCD, CDA, DAB

If I need to find the number of groups in which one member (say A) is always present, I can calculate manually from the options above = 3 (ABC, CDA, DAB)

Applying your method, I calculate it a follows:
A _ _ = 1 * 3 * 2 = 6.

But I need to divide by 2!, as there is 1 fixed member(A) and I need to pick only two people to go with A = 6/2! = 3 (same as above).

This is great. Thanks a lot Ron!

[RonPurewal]

sure. if you have any other questions, feel free to ask.