0
$\begingroup$

You are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?

I think I can start off by putting 1 ball into each box so I get n-k balls left. K out of the N balls can be put in the boxes in n!/(n-k)! ways and that's the farthest I got. I don't know how to proceed. Any help appreciated.

$\endgroup$
  • 1
    $\begingroup$ This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract. $\endgroup$ – Arturo Magidin Nov 20 '18 at 20:14
  • $\begingroup$ And how would I do what you suggested? $\endgroup$ – Sartr Nov 20 '18 at 20:44
  • 1
    $\begingroup$ Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc. $\endgroup$ – Arturo Magidin Nov 20 '18 at 20:50
  • 1
    $\begingroup$ Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2. $\endgroup$ – Arturo Magidin Nov 20 '18 at 21:08
  • 1
    $\begingroup$ So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times. $\endgroup$ – Arturo Magidin Nov 20 '18 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.