Inclusion - Exclusion Problem - Suppose that a person with seven friends...

Question

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.

Answer 1

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

Answer 2

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