inclusion-exclusion problem - dinner arrangement

92 Views Asked by At

I'm working on my combinatorics assignment and I don't fully understand this question:

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?

So, the answer is : $$P(7C3,7)-7P(6C3,7)+(7C2) \cdot P(5C3,7)$$

I get it. It's just a little detail I am missing. Why can't I expand the equation with $-(7C3)\cdot P(4C3,7)+(7C4) \cdot P(3C3,7)$? I mean, $3$ friends are invited so for the exclusion, can't I count exclusion of $4$ friends? I'm definitely misunderstanding something here.

1

There are 1 best solutions below

2
On BEST ANSWER

You can expand the equation as you suggested, but the terms you're adding are zero. Notice that $4C3<7$, and $3C3<7$, so you can't form a permutation of seven triplets if there aren't at least seven triplets to start with. OTOH $5C3$ is ten, which exceeds seven.