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$
  • 1
    $\begingroup$ The cases where he invites everyone but Alice, everyone but Bob, everyone but Carol, ... $\endgroup$ – saulspatz Oct 31 '18 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 '18 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 '18 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 '18 at 3:54
  • $\begingroup$ Isn't there a term missing? What about the case where he omits $3$ friends? $\endgroup$ – saulspatz Oct 31 '18 at 3:56
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$
  • $\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 '18 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$ – Thomas Bladt Oct 31 '18 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 '18 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$ – Thomas Bladt Oct 31 '18 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.