# Enumerating the ways of distributing n balls into k boxes 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. 