1
$\begingroup$

Suppose that a person with 7 friends invites a different subset of three friends to dinner every night for 7 consecutive evenings. How many ways can this be done so that each friend is included at least once?

I'm really lost on this problem. I would assume you would assign three friends to each of the seven nights in a manner such that each night the person invites a unique group of three friends. In other words I would assume that if ABC are invited on night one then BCD is a fair choice for night 2 but not BCA (order doesn't matter). We would also have to ensure that each of the friends are included at least once in the 7 nights of invites. I would try to start by listing each of the seven friends on separate nights: A B C D E F G and then I would try to arrange the other two friends per each night in a way so that no two of the 7 nights have three identical letters (regardless of the order). I'm just not sure how to go about doing that...

$\endgroup$
1
$\begingroup$

There's an easier way of doing this via inclusion-exclusion. The idea is this: of the $7\choose 3$ subsets of friends, we can count the number of ways to take a list of $7$ of them. However, it is possible that these lists could exclude a friend, so we want to count the number of bad cases where we take out a friend. If we exclude friend $i$, there are $6\choose 3$ subsets of friends, and we can count the number of ways to take a list of $7$ of them, thereby excluding friend $i$. We can then take out these bad cases from our original count of lists.

However, there is a problem: consider the list $\{a,b,c\}, \{a,b,d\}, \{a,b,e\}, \{b,c,d\}, \{b,c,e\}, \{a,d,e\}, \{a,c,e\}$. This list excludes both $f$ and $g$. When we count the bad lists that exclude $f$, we subtract it once from our total, but when we count the bad lists that exclude $g$, we subtract it a second time. That means we double counted it when we subtracted it from our total, so we need to add these bad cases back once. Thus, for each pair of friends, we count the number of ways to take lists of the $5\choose 3$ subsets that exclude both of those friends, and add them back to our total. That will give us our answer. Note that we can stop here because there is never a case where we exclude $3$ different friends, since there are only ${4\choose 3}=4$ subsets that exclude them.

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