# Inclusion - Exclusion Problem - Suppose that a person with seven friends…

Can someone please explain to me how to approach this problem:

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

I can't think of a good way to break this down into cases. Thanks for the help.

• So in how many ways can he invite friends without the condition? Take that and take out the chances of never invite friend 1, adjoint the chances to never invite friend 2... So you will end up counting something like $|A\setminus A_1\cup A_2\cup A_3\cup A_4\cup A_5\cup A_6\cup A_7|$ where A are all the possibilities and $A_i$ are the possibilities without taking into account friend $i$. – Phicar May 6 '16 at 3:30
• So then would A be something like: P( C(7, 3), 7) ? since you are choosing three friends each day, and there are 7 days in the week. This is part of the answer the textbook gives, which I'm trying to understand: P( C(7,3), 7) - 7 * P( C(6,3), 7) + C(7,2)P( C(5,3), 7) – user337384 May 6 '16 at 3:36
• Well, that depends i would say: ${{7}\choose {3}}^7$ if we allowed the same set of friends in two nights. If you do not allow that, there will be what you said. – Phicar May 6 '16 at 3:43

For each set of $k$ friends ($k \ge 3$), the number of ways to invite three of these friends each night (thus excluding the remaining $7-k$ friends, and maybe more) is ${k \choose 3}^7$. The number of ways excluding at least one friend is $$\sum_S (-1)^{|S|} {|S| \choose 3}^7 = \sum_{k=3}^6 (-1)^{k} {7 \choose k} {k \choose 3}^7$$ where the sum is over all subsets $S$ of at least $3$ friends. The number of ways where nobody is excluded is then $$\sum_{k=3}^7 (-1)^{k+1} {7 \choose k} {k \choose 3}^7$$

For $d$ days, you want to invite $f$ friends $n$ at a time. There are

$$T = {f \choose n}^d$$

ways to make this choice. Except that you might not have invited everyone. Let $E_g$ be all the invations arrangements where friend $g$ is excluded. Doing the same calculation as above with the friend missing you get:

$$|E_g| = {f \choose n - 1}^d$$

And $|E_{g_1} \cap E_{g_2}| = {f \choose n - 2}^d$, further $|E_{g_1} \cap E_{g_2} \cap E_{g_3}| = {f \choose n - 3}^d$, etc.

You want to compute $T - |E_{g_1} \cup E_{g_2} \cup \dots E_{g_f}|$. Applying inclusion exclusion you get:

$$\begin{array} {rl} % |E_{g_1} \cup \dots \cup E_{g_f}| = &|E_{g_1}| + |E_{g_2}| + \dots \\ % - &|E_{g_1} \cap E_{g_2}| - |E_{g_2} \cap E_{g_3}| - \dots \\ % + &|E_{g_1} \cap E_{g_2} \cap E_{g_3}| + |E_{g_1} \cap E_{g_2} \cap E_{g_4}| + \dots \\ % \vdots \end{array}$$

which is :

$$|E_{g_1} \cup \dots \cup E_{g_f}| = f~|E_{g_1}| - {f \choose 2}~|E_{g_1} \cap E_{g_2}| + {f \choose 3}~|E_{g_1} \cap E_{g_2} \cap E_{g_3}| - \dots$$

where the last term will be $(-1)^{f - n}~{f \choose f - n}~E_{\{1,~\dots,~f-n\}}$ because there are zero ways to exclude more than $f-n$ friends if you are inviting $n$ each time. So the count is

$$\sum_{k=0}^{f - n} (-1)^k ~ {f \choose k} {f \choose n - k}^d$$