50 people with different names, Lorenzo, Sara , Kate , Kevin, ….. should be divided into 6 numbered groups. How many ways can this be done if the groups are to be such that
- none of the groups can be empty and
- Lorenzo and Sara cannot be in the same group and
- Sara and Kate cannot be in the same group.
So we can already see that it's 50 distinct objects into 6 numbered bins.
So my solution to that none of the groups can be empty is. 50!/45! since we only need to fill the first 5 groups with just 1 person, and the remaining group is where i put the rest. So it should be a multinomial coefficient.
50!/1!1!1!1!1!45! = 50!/45!
- Lorenzo and Sara cannot be in the same group and
This is where I get stuck since now I need to fullfill the previous condition. I was thinking of some sort of Principle of Inclusion Eclusion type of problems, but I'm not sure how to set it up.
I was thinking of |Numbers of ways without L&S| = 50!/45! – |Numbers of way with L&S|
Cheers! 🙂
Best Answer
Inclusion-exclusion over the events "Group1 is empty", "Group2 is empty", ... , "Group6 is empty" but keep track of all events including the events "L and S in same group" and "K and S in same group." For convenience sake, write out all where we had neither of these final two events first... then follow it by where we had exactly one of these final two events, and lastly do it where we had both.
$\left(6^{50}-\binom{6}{1}5^{50}+\binom{6}{2}4^{50}-\binom{6}{3}3^{50}+\binom{6}{4}2^{50}-\binom{6}{5}1^{50}\right) - 2\left(6^{49}-\binom{6}{1}5^{49}+\binom{6}{2}4^{49}-\binom{6}{3}3^{49}+\binom{6}{4}2^{49}-\binom{6}{5}1^{49}\right) +\left(6^{48}-\binom{6}{1}5^{48}+\binom{6}{2}4^{48}-\binom{6}{3}3^{48}+\binom{6}{4}2^{48}-\binom{6}{5}1^{48}\right)$
Recognize that each of these parenthetical phrases matches the answer to the problem had we ignored these final two events and that these can be simplified using stirling numbers of the second kind:
$({50 \brace 6} - 2{49\brace 6} + {48 \brace 6})6! = 560965392866494641023205785898674256720$
Compare this to the approximation by trueblueanil's probability argument of it being $\frac{5^2}{6^2}{50\brace 6} = 560936381547005993727389118856408343500$, an error of approximately $0.005\%$
The take away is that one should be careful about assuming independence and uniformity, but with numbers as large as these one could and should expect that the error caused by such an assumption should be miniscule. It is still an error however.