# Enumerating the ways of distributing n balls into k boxes

Raymond Chen

Suppose you had n indistinguishable balls and k distinguishable boxes. Enumerate the ways of distributing the balls into boxes. Some boxes may be empty.

We can represent each distribution in the form of n stars and k − 1 vertical lines. The stars represent balls, and the vertical lines divide the balls into boxes. For example, here are the possible distributions for n = 3, k = 3:

 ***|| 3+0+0 **|*| 2+1+0 **||* 2+0+1 *|**| 1+2+0 *|*|* 1+1+1 *||** 1+0+2 |***| 0+3+0 |**|* 0+2+1 |*|** 0+1+2 ||*** 0+0+3

This visualization is known in combinatorics circles as stars and bars.

From this visualization, we see that what we are doing is taking n + k − 1 slots, and in each slot placing a star or a bar, subject to the constraint that there be n stars and k − 1 bars. Another way of looking at this is that we are choosing a subset of size k − 1 from a set of size n + k − 1 (the subset specifying where the bars go).

Now we can fire up our subset-generating machine.

```function Distributions(n, k, f) {
Subsets(n + k - 1, k - 1, function(s) {
s.push(n + k);
f(s.map(function(v, i) { return v - (s[i-1]||0) - 1; }));
s.pop();
});
}
```

We ask to generate subsets of size k − 1 from a set of size n + k − 1. For each such subset, we draw an artificial bar at the end (slot n + k), then calculate the number of stars between the bars. The number of stars between two bars is the distance between the two bars, minus 1 because the bar takes up space, too.

Another solution is to reduce this to a problem we already know how to solve: enumerating integer compositions. After distributing the balls into boxes, we go around like Santa Claus and give each box one extra ball, which produces a composition. Conversely, for any composition, remove one ball from each box, and you get a distribution.

```function Distributions(n, k, f)
{
Compositions(n + k, k, function(s) {
f(s.map(function(v) { return v - 1; }));
});
}
```

We added k extra balls, so we need to generate compositions of n + k. When we get each composition, we take one ball away from each box and call that the distribution.