Dinner invitation problem combinatorics

Question

A man has eight friends $A$, $B$, $C$, $D$, $E$, $F$, $G$ and $H$. He would like to invite three of them for dinner. If $A$ and $B$ must be together, i.e. he cannot just invite one of them, but $C$ must not come with $D$, i.e. he cannot invite both of them, then how many different invitations can he make?

I was thinking that the original combination should be $ ^{8} C_{2}$ , and then I should progress somehow using the addition rule, but in the solutions I was given it says $ ^{6} C_{1}$ instead. Could someone explain why?

Answer 1

Add up the following:

• Number of combinations with A and B: $\binom{8-2}{3-2}=6$
• Number of combinations with C but without A or B or D: $\binom{8-4}{3-1}=6$
• Number of combinations with D but without A or B or C: $\binom{8-4}{3-1}=6$
• Number of combinations without A or B or C or D: $\binom{8-4}{3-0}=4$

The answer is therefore $6+6+6+4=22$.

Answer 2

I would think of this as a "subsets" problem: the friends he invites to dinner form a subset of the set of all friends. In general, if a set contains n elements then it has $2^n$ subsets. To include the constraints, "A and B must be together" and "C must not come with D", think of "AB" as a single element and "CD" as a single element. Then "the set of all friends" contains 6 elements, "AB", "CD", "E", "F", "G", and "H", so has $2^6= 64$ subsets. But where "C" and "D" are concerned we can invite either C or D but not both so that every subset the contains "CD" can be treated as either "C" or "D". That multiplies the number of possible subsets by 2. There are 128 different ways to invite friends. (That includes the empty set. If you do not want to include "invite no one" as a "dinner", there are 127 ways.)

Answer 3

Can you please post the complete answer given by the book?

As far as starting with $6\choose 1$, the idea here is that you are counting the number of ways to invite $AB$. Thus you remove $A$ and $B$ and then $6$ guests remain of which you need one more to make $3$.

Now consider the remaining invitations, we can remove $AB$ from consideration since we've counted all possible invitations with them together and they can't be invited otherwise.

So then let's count the remaining ways to invite $3$ guests. Since $C$ and $D$ can't come together let's remove them and count each case.

Case 1. We invite $D$. Then there are $4\choose 2$ guests remaining we can group with $D$.

Case 2. We invite $C$. Then there are $4\choose 2$ guests remaining we can group with $C$.

Case 3. We invite neither $D$ nor $C$. Then there are $4\choose3$ invitations we can form.

Thus our answer is

$$\binom{6}{1}+ \binom{4}{2} + \binom{4}{2} + \binom{4}{3} $$