Inviting 4 friends out of 8 for a week such that each friend visits at least once

121 Views Asked by At

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once.

Let's number the friends for brevity, 1 to 8.

This is like asking how many permutations there are for 4 digits out of 8, 7 times such that each digit appears at least once.

I don't think I can solve this directly so I'll be using inclusion exclusion and a complement. The complement is at least one friend didn't visit.

The general case: 7 days a week, 4 digits out of 8: $7\cdot (8\cdot 7 \cdot 6 \cdot 5)$

One friend wasn't invited: $7\cdot ( 7 \cdot 6 \cdot 5\cdot4)$ and there are $8$ possibilities for a friend that weren't invited.

Two friends: $7\cdot ( 6 \cdot 5\cdot4\cdot3)$ and there are $8\cdot 7$ possibilities for two friends that wasn't invited.

Three friends: $7\cdot ( 5\cdot4\cdot3\cdot2)\cdot 8\cdot 7\cdot 6$

Four friends: $7\cdot ( 4\cdot3\cdot2\cdot1)\cdot 8\cdot 7\cdot 6\cdot5$

There can't be more friends that weren't invited.

The total would be: $\text{general case} - (\text {ones} - \text {twos}+\text {threes}-\text {fours})$.

Is that alright?

1

There are 1 best solutions below

0
On

No, this is wrong. It's not entirely clear from the question whether the order during the same day matters, but I would have interpreted the question such that it doesn't. In this case, it should be $\binom84$ where you have $8\cdot7\cdot6\cdot5$.

The more severe problem is that the number of ways of doing this $7$ times is not $7\cdot\binom84$ but $\binom84^7$. Correspondingly, if $k$ friends were never invited, that counts for $\binom{8-k}4^7\binom8k$ ways. Here there is certainly no such thing as the order in which they were not invited, so your falling factorials instead of binomial coefficients are wrong.