0
$\begingroup$

Find the number of ways in distributing $8$ distinct balls into $6$ distinct boxes such that there is at least $1$ ball in each box.

We are well acquainted with the traditional Inclusion-Exclusion principle in solving this and it will come up as $191520$ ways.

I tried in this way:

When we distribute $8$ balls into $6$ boxes we have two possible cases

Case $1.$ There are exactly $2$ boxes with $2$ balls each

Case $2.$ There is exactly $1$ Box with $3$ balls in it.

For Case $1$, the distribution is done by choosing $2$ boxes from $6$ boxes and $2$ balls from $8$ balls and those two balls can be arranged in $2!$ ways. But I require another two balls from remaining $6$ balls to be placed in each of these two boxes which can be done in $\binom{6}{2} \times 2!$ ways. Finally remaining $4$ balls can be distributed in remaining $4$ boxes in $4!$ ways. So total number of ways for Case $1.$ is

$$\binom{6}{2} \times \binom{8}{2} \times 2! \times \binom{6}{2} \times 2! \times 4!=604800$$

For Case $2$, the number of ways is

$$\binom{6}{1} \times \binom{8}{3} \times 5!=40320$$

I am pretty sure the value obtained for Case $2.$ is correct. but I could not find where I went wrong in Case $1.$

$\endgroup$
1
  • $\begingroup$ Your description is somewhat unclear. You say "We are well acquainted with the traditional Inclusion Exclusion principle in solving this and it will come up as $191520$ ways". So how can the different value that you've obtained for case #$2$ can be correct??? $\endgroup$ Dec 4 '15 at 14:17
1
$\begingroup$

On the case 1 you must choose first $2$ boxes over $6$ i.e. $C(6,2)$ and after for the first box you choose $(8\cdot 7)/2!$ and after $(6\cdot 5)/2!$ for the second box, and in third place you count the permutations of the others boxs that is $4!$, so the total is $\binom{6}{2}^2\cdot \binom{8}{2}\cdot4!=15^2\cdot 28\cdot 24=151200$.

And $151200+40320=191520$ as stated.

$\endgroup$
0
$\begingroup$

Case 1 is wrong: you pick 2 boxes from 6, in $\binom{6}{2}$ ways. These boxes are different, say boxes $i < j$. First fill box $i$ with 2 balls out of 8, so $\binom{8}{2}$ ways. Then fill box $j$ with 2 out of 6, so $\binom{6}{2}$ ways. Then we are left $4!$ ways for the remaining 4 balls in the remaining 4 boxes.

It only matters that balls say 7 and 5 are in box $i$, there is no order within that box! So we get a number 4 times as small, and then it checks out with your other answer.

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