1
$\begingroup$

Suppose that a person with seven friends invites a different subset of three friends to dinner every night for one week (seven days). How many ways can this be done so that all friends are included at least once?

I know the number of ways to do this with no restriction is $\binom{7}{3}^7$.

I need to use Inclusion-Exclusion..however I am having trouble determining the sets to use.

$\endgroup$
10
  • 1
    $\begingroup$ The cases where he invites everyone but Alice, everyone but Bob, everyone but Carol, ... $\endgroup$
    – saulspatz
    Oct 31, 2018 at 3:43
  • $\begingroup$ yeah so $A_1=\{\text{invites everyone except F_1}\}$ and $A_2=\{\text{invites everyone except F_2}\}$...up until $A_7$ but then how do I find the ways each of those can be done $\endgroup$
    – rover2
    Oct 31, 2018 at 3:46
  • 1
    $\begingroup$ Same way you did it when he invited all seven friends -- now there are only six. $\endgroup$
    – saulspatz
    Oct 31, 2018 at 3:47
  • $\begingroup$ so would it be $\binom{7}{3}^7 - 7\binom{6}{3}^7 + 21\binom{5}{3}^7 -35\binom{4}{3}^7+35$? $\endgroup$
    – rover2
    Oct 31, 2018 at 3:54
  • $\begingroup$ Isn't there a term missing? What about the case where he omits $3$ friends? $\endgroup$
    – saulspatz
    Oct 31, 2018 at 3:56

2 Answers 2

4
$\begingroup$

We will solve this using the Inclusion-Exclusion Principle.

Since the person has $7$ friends, each night he/she has $\binom{7}{3}$ possible groups of friends he/she can invite over. Notice he/she will do this for $7$ nights, but the groups have to be different every night. Thus we have to consider the permutations of $7$ groups of friends (from the possible $\binom{7}{3}$ groups). This yields $P\left(\binom{7}{3},7\right) $. This is the total number of ways for the person to invite different groups of $3$ friends each night, for $7$ nights.

Now we have to subtract the number of cases where the person omits one friend. Using exactly the same arguments as before, there is a total of $P\left(\binom{6}{3},7\right)$ ways to do so. Since we can choose the friend to omit in $\binom{7}{1} = 7$ ways, we have to subtract $ \ \ 7 \times P\left(\binom{6}{3},7\right)$ to the total.

Now we add the number of ways where the person omits two friends. By the same reasoning as before, this turns out to be $\binom{7}{2}\times P\left(\binom{5}{3},7\right)$.

Notice that the next step is to subtract the case where the person omits $3$ of their friends. But then we would be left to choose from $4$ friends to invite. There are only $\binom{4}{3} = 4$ different groups of $3$ we can form, and we need to have at least $7$ (one for every night), so we can stop here.

So, by the Inclusion-Exclusion Principle, the answer is given by $$P\left(\binom{7}{3},7\right) - 7 \cdot P\left(\binom{6}{3},7\right) + \binom{7}{2}\cdot P\left(\binom{5}{3},7\right).$$

$\endgroup$
4
  • $\begingroup$ I follow this OK, up to the point of adding back in the number of ways to omit 2 friends. Why add and not subtract? I get the inclusion-exclusion method but does subtracting the number of ways to omit 1 friend include subtracting double the number of ways of omitting 2 friends? Am I missing something? $\endgroup$
    – Phil H
    Oct 31, 2018 at 14:04
  • $\begingroup$ This is how Inclusion-Exclusion works. We first count the total possible number of ways to invite groups of $3$ friends. Sometimes, one friend will never be invited, so we remove those cases from our total. Now consider: $\{ c,d,e\}, \{ c,d,f\}, \{e,f,g \}, \{ c,f,g\}, \{ d,f,g\}, \{c,e,f \}, \{ d,e,f\}$, where each letter is a friend. Here $a$ and $b$ have not been invited. When counting the times when $a$ has not invited, we remove this possibility once, but we remove it again whilst counting the times where $b$ has not been invited. We have to add one again to account for double counting. $\endgroup$
    – Bergson
    Oct 31, 2018 at 15:42
  • $\begingroup$ You missed out ${cdg},{ceg},{deg}$ but yes I get it now. These 10 three letter combinations were already considered when omitting a and again when omitting b, which is twice, so they have to be added back again. Thanks. $\endgroup$
    – Phil H
    Oct 31, 2018 at 18:14
  • $\begingroup$ It's true that there are $10$ combinations of size $3$ of the letters in the set$\{c,d,e,f,g\}$. However, notice that this is an example of different groups of $3$ friends that he can invite over during $7$ nights, hence why we should only include $7$ groups and not all the possible $10$. I think you get the main idea though. $\endgroup$
    – Bergson
    Oct 31, 2018 at 18:22
0
$\begingroup$

This answer is essentially the same as Thomas Bladt's but I use a different format for counting. $$\frac {\binom{7}{3}!}{(\binom{7}{3}-7)!} - 7\cdot \frac{(\binom{7}{3}-\binom{6}{2})!}{(\binom{7}{3}-\binom{6}{2}-7)!}+ \binom{7}{2}\cdot \frac{(\binom{7}{3}-\binom{6}{2}-\binom{5}{2})!}{(\binom{7}{3}-\binom{6}{2}-\binom{5}{2}-7)!}$$ Which reduces to.....

$$\frac{35!}{28!}-7\cdot \frac{20!}{13!} + 21\cdot \frac{10!}{3!}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .