a commitee of 3 people is to be chosen

[shalinibhatia15]

A commitee of 3 people is to be chosen from 4 married couples.What is the number of different commitees that can be chosen if 2 people who are married to each other cannot both serve on the commitee?

A 16

B 24

C26

D 30

E 32

[RonPurewal]

first, note that this problem can't be solved with the traditional combination and permutation formulas.

however, this problem can be solved by the "slot method", in which you create a slot for each decision that you have to make in the problem. we are choosing a committee of three people, so we make three slots:
___ ___ ___

for the first slot, anyone can be chosen.
_8_ ___ ___

once this person has been chosen, there are now TWO people ineligible for the next slot: the person who has actually been chosen already, AND that person's spouse (note that no married couple is allowed to serve together on the committee). so there are only six people eligible for the second slot.
_8_ _6_ ___

for the same reason as above, once these two people have been chosen, there are now only four people eligible for the last slot.
_8_ _6_ _4_

finally, since order doesn't matter in this problem (i.e., it's okay to scramble the people on the committee once you have chosen them), we have to divide by the factorial of th number of choices:
(8 x 6 x 4) / 3!
= 8 x 4 (since 3! equals 6)
= 32

--

for a much more comprehensive treatment of combinatorics -- including a more in-depth treatment of the slot method and the "divide by factorials" step -- check out our thursday study hall recordings:
http://www.manhattangmat.com/thursdays-with-ron.cfm
the combinatorics information may be found in the recording for thursday, december 3, 2009.

[abemartin87]

Hey ron,

I solved the problem the same way. But I also like attacking the problem from different methods.

=====1st Method============
Lets say that I first want to find the total number of combinations of picking the three members then subtract out the number of ways a married couple can appear in the three committtie.

So the total number of ways of selecting the three members is 8C3=56.
Now the total number of ways we can have a married couple is

8 _ 1 _ 6

The first slot is for any of the 8 people. The second person has to be the first persons couple, so it equals 1. The last slot is any of the remaining 6.Lastly, since order doesnt matter we divide by 3!. to Get 8.

But 56-8=48 not the answer.

=====Second Method=========
The second method i used to takle the number of ways we can have a married couple in the 3 slots is we first choose one couple out of the 4 --- 4C1. We have 3 slots to place the 2 married couples -- 3C2. And for the last slot we can choose any of the remaining 6 -- 6C1.

We get (4C1)*(3C2)*(6C1)=72 . Way above the possible number of permutations. What am I doing wrong?

[RonPurewal]

=====1st Method============
Lets say that I first want to find the total number of combinations of picking the three members then subtract out the number of ways a married couple can appear in the three committtie.

So the total number of ways of selecting the three members is 8C3=56.
Now the total number of ways we can have a married couple is

8 _ 1 _ 6

The first slot is for any of the 8 people. The second person has to be the first persons couple, so it equals 1. The last slot is any of the remaining 6.Lastly, since order doesnt matter we divide by 3!. to Get 8.

mistake is in purple.

when you look at "order doesn't matter" situations, you divide by the factorial(s) of how many indistinguishable "slots"/positions are being chosen.
when you specify that you're choosing a married couple and a single person, there are only *two* indistinguishable slots (= the two slots in the married couple). the third slot -- which is designated for a single person -- is distinct from the other two.
so, you would divide 8*1*6 by 2!, not by 3!. therefore, you would get
56 - 8*1*6/(2!)
= 32

notice that there's an easier way to do this calculation: you want the number of ways to get a married COUPLE and then a single PERSON.
there are 4 ways to get a married couple (since there are 4 such couples) -- there's no reason to break this down into the 2 individual people.
then, there are 6 individuals remaining.
so, this is just 4*6 = 24. therefore, 56 - 24 = 32.

=====Second Method=========
The second method i used to takle the number of ways we can have a married couple in the 3 slots is we first choose one couple out of the 4 --- 4C1. We have 3 slots to place the 2 married couples -- 3C2. And for the last slot we can choose any of the remaining 6 -- 6C1.

there's the issue.

when you use the slot method, you don't consider different rearrangements of the slots themselves. so, if you are doing this as "married, married, single", then that's THE way you've chosen to do it. if someone else chooses to do it as "single, married, married", then that will work, too -- but you have to choose one formation for the slots, and then stick to it.

here's a really simple example:
let's say i have 4 shirts and 5 pairs of pants.
that's 20 outfits, right?
the problem with your approach is that you'd think it's 40 outfits -- with your approach, you'd get 20 for shirts*pants, and then another 20 for pants*shirts.
that's not how the method works. you just have to designate either pants*shirts or shirts*pants, and then stick with it. either way, you get 20.

[chriswearnjunk]

What I don't get is why you divide by 3! instead of 3!5!. That would be same denominator as in the combinations formula, and makes sense in my head because you are essentially assigning 3 "you're in" designations and 5 "you're out" designations to 8 people, each of which are identical.

[RonPurewal]

What I don't get is why you divide by 3! instead of 3!5!. That would be same denominator as in the combinations formula, and makes sense in my head because you are essentially assigning 3 "you're in" designations and 5 "you're out" designations to 8 people, each of which are identical.

yeah, but, in the expression above ...
(8 x 6 x 4)/3!
... you are not in any way whatsoever accounting for the "you're out" people, in either the numerator or the denominator. so, there you go.
if you reallyreallyreally wanted to include the "you're out" people here -- there's no reason to do so, but if it makes the situation seem more clear you certainly can -- then you'd have to put them into both the numerator and the denominator, giving you
(8 x 6 x 4)(5 x 4 x 3 x 2 x 1) / (3!5!)
... which is of course the same as what's already up there, except with substantially more work involved in simplifying it.

--

the "combinations formula" you're talking about here is inefficient by design -- it can ALWAYS be reduced to an expression with only one factorial in the denominator. for instance, 8!/(3!5!) is the same as just (8 x 7 x 6)/3!.

in fact, the only reason why the combinations formula even exists, as such, is because it's visually pretty.
yes, seriously. it's because mathematicians would rather look at
n!/((n - r)!r!)
than at
(n)(n - 1)(n - 2)...(n - r + 1)/r!
even though the latter is more simplified.

[rustom.hakimiyan]

first, note that this problem can't be solved with the traditional combination and permutation formulas.

however, this problem can be solved by the "slot method", in which you create a slot for each decision that you have to make in the problem. we are choosing a committee of three people, so we make three slots:
___ ___ ___

for the first slot, anyone can be chosen.
_8_ ___ ___

once this person has been chosen, there are now TWO people ineligible for the next slot: the person who has actually been chosen already, AND that person's spouse (note that no married couple is allowed to serve together on the committee). so there are only six people eligible for the second slot.
_8_ _6_ ___

for the same reason as above, once these two people have been chosen, there are now only four people eligible for the last slot.
_8_ _6_ _4_

finally, since order doesn't matter in this problem (i.e., it's okay to scramble the people on the committee once you have chosen them), we have to divide by the factorial of the number of choices:
(8 x 6 x 4) / 3!
= 8 x 4 (since 3! equals 6)
= 32

Hi Ron,

I have a question regarding the "order doesn't matter" part. Please bare with me as I try to explain my thought process/question.

When we do the "slot" method, you're inherently saying that order matters. Is that correct? Now, if I flip this around and just add a part to the question stem saying "what is the probability that the above selection would work", I would guess that I would solve the problem something like this:

(8/8)(6/7)(4/6) * 3! -- is that correct?

The confusion comes in with the 3! -- why are we MULTIPLYING by the permutation when it comes to probability but DIVIDING by the permutation when looking at the combinations?

Additionally, if I solved using a different method, it would be something along the lines of (8c8)(7c6)(6c4)/(8c3) -- in this case, I simply ignore the permutation part all together?

I apologize for the trivial questions -- just trying to connect the dots.

Thanks!

[qqixiaofan]

Hi,
Here is how i see the problem in my head. And please do let me know if the logic is incorrect.
(1) within each couple, we need to chose one ppl for the commitee, so the combination is 1 out of 2: 2C1 = 2
(2) There are three couples, each has 2 ways to chose one member, so 3 couple =2*2*2=8
(3) There are 4 couples, we need to chose 3 out of 4. The combination of 4C3 = 4
(4) finally: 8*4=32

[RonPurewal]

Hi,
Here is how i see the problem in my head. And please do let me know if the logic is incorrect.
(1) within each couple, we need to chose one ppl for the commitee, so the combination is 1 out of 2: 2C1 = 2
(2) There are three couples, each has 2 ways to chose one member, so 3 couple =2*2*2=8
(3) There are 4 couples, we need to chose 3 out of 4. The combination of 4C3 = 4
(4) finally: 8*4=32

Technically, though, the steps don't work in this order. For this approach to make sense, the steps should be done in the order 3, 1, 2, 4.
I.e., you can't actually pick the people from the couples (steps 1 and 2) until you've already chosen the couples from which to choose them (step 3).

But, yes, this is a workable approach.

[qqixiaofan]

Hi,
Here is how i see the problem in my head. And please do let me know if the logic is incorrect.
(1) within each couple, we need to chose one ppl for the commitee, so the combination is 1 out of 2: 2C1 = 2
(2) There are three couples, each has 2 ways to chose one member, so 3 couple =2*2*2=8
(3) There are 4 couples, we need to chose 3 out of 4. The combination of 4C3 = 4
(4) finally: 8*4=32

Technically, though, the steps don't work in this order. For this approach to make sense, the steps should be done in the order 3, 1, 2, 4.
I.e., you can't actually pick the people from the couples (steps 1 and 2) until you've already chosen the couples from which to choose them (step 3).

But, yes, this is a workable approach.

Thanks for the confirmation

[RonPurewal]

Sure.