Person with seven friends invites subset of three for one week

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.

• The cases where he invites everyone but Alice, everyone but Bob, everyone but Carol, ... – saulspatz Oct 31 '18 at 3:43
• 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 – rover2 Oct 31 '18 at 3:46
• Same way you did it when he invited all seven friends -- now there are only six. – saulspatz Oct 31 '18 at 3:47
• so would it be $\binom{7}{3}^7 - 7\binom{6}{3}^7 + 21\binom{5}{3}^7 -35\binom{4}{3}^7+35$? – rover2 Oct 31 '18 at 3:54
• Isn't there a term missing? What about the case where he omits $3$ friends? – saulspatz Oct 31 '18 at 3:56

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).$$

• 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? – Phil H Oct 31 '18 at 14:04
• 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. – Thomas Bladt Oct 31 '18 at 15:42
• 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. – Phil H Oct 31 '18 at 18:14
• 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. – Thomas Bladt Oct 31 '18 at 18:22

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!}$$