Friday, March 13, 2015

A problem with balls and boxes

The problem

Combinatorial problems can be simply to state, and difficult to solve. But this one has a surprisingly simple solution, if you reframe it a bit.

The problem is: in how many ways you can place $k$ identical balls in $n$ distinct boxes? We assume that each box is large enough so that you can place all balls in it, so we have to count also the cases with empty boxes. You have to place all balls in boxes.

Yesterday, a friend and fellow physicist told me the problem, he needed to solve it in order to count some quantum states, but this is not relevant here. He solved it before, but forgot how. He found an ingenious way to see what happens if we add a new box or a ball. This would lead to some recurrence formula, which involved summing both over the number of balls, and the number of boxes. So he asked me to help him with these calculations. This is a problem of induction, which anyone should be able to resolve in high school, but I considered that all these calculations were too tedious for me, especially since I wanted to have lunch. So I replied that I would rather prefer to find a direct way to the solution, by framing it differently.

Before reading the solution, I would like to ask you to solve it yourself.

The solution

We can reframe the problem like this. We can arrange the boxes one next to another, like the carts of a train. Then we get something like this:

Now we can invent a notation for each configuration: we denote every space between boxes with a square, and every ball with a circle. Here's what we get:

The sequence starts with a separator, because the first box is empty. Then there are four balls in the second box. There are two successive separators because the third box is empty. Then there's a box with two balls, and the last contains only one ball.

It is easy to see now that we have $n-1+k$ objects, $k$ of them being the balls, and $n-1$ of them being the separators. Since the conditions of the problem allow to place them in any order, the problem becomes equivalent with choosing $k$ out of $n-1+k$. So the result is $n-1+k$ choose $k$, which is $\displaystyle{\frac{(n-1+k)!}{(n-1)!k!}}$.

You may try to solve it by double induction, and at the end the result may look more complicated, unless you are able to apply some formulas to bring it in this simple form.

No comments: