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:

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.

Raymond Chen

Follow