Enumerating the ways of distributing n balls into k boxes

Raymond Chen

Raymond

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.

Raymond Chen
Raymond Chen

Follow Raymond   

0 comments

Comments are closed.