Balls In Bins With Limited Capacity

Given n indistinguishable balls and m bins, where each bin has a capacity of c(i) (i = 1 to m) balls, in how many ways can the n balls be distributed in the m bins? Note that n ≤ sum of c(i)'s; one or more bins may have room for all n balls; we don't care which balls are in which bins, nor do we distinguish between positions in the bins; and bins need not be occupied.

Before describing the traditional combinatorial approach to this problem, let's try something a little different. First, if N(k) denotes the number of ways of packing k balls into m bins with capacities c(i), i=1 to m, then we have

where c is the total capacity c(1) + c(2) + .. + c(m). For example, if we have 5 bins with capacities 3,2,5,4,2 respectively, then c = 16 and the values of N(k) for k = 0 to 16 are as shown below:

(Naturally we have N(k) = N(c–k), because the distribution of empty spaces is symmetrical with the distribution of balls.) The total of these values of N(k) is 1080, which can be computed directly as a function of the individual bin capacities by equation (1) as

An interesting aspect of the values of N(k), for relatively small perturbations from uniform capacities, is that they approach a normal distribution with a mean of c/2. In fact, we can use this feature to give an approximate formula for N(k). Letting A denote the sum of the values of N(k) as given by (1), solve the equation

for z, and set s = (c/2 + 1)/z. Then the individual values of N(k) are given approximately by

For example, to determine the number of ways of distributing 11 balls into 5 bins with the capacities 3, 2, 5, 4, 2, we have c = 16 and we compute A = 1080 from equation (1). Then equation (2) gives z = 3.169, from which we compute s = 2.840. Inserting these values into equation (3) gives

For k = 11 we get N(11) = 87, compared with the true value of 90. For larger numbers of bins and greater total capacity, the probability of roughly uniform capacities increases, assuming the capacities are randomly chosen, so the true results approach more and more closely a normal distribution and the approximation gets progressively better.

This approach is reasonably valid if the bins all have roughly the same capacity, but if one c(i) is much larger than the others, N(k) will tend to look very flat around k = half the product of (c(i)+1). Hence the normal approximation applies only to relatively small perturbations around the condition of uniform capacities. For a more generally applicable answer, we turn now to the more traditional combinatorial techniques.

One possible combinatorial approach would be to observe that N(k) can be interpreted as the number of lattice points contained in the intersection of an m-dimensional block (one corner at the origin, other corners at (c(1),0,..0), (0,c(2),0,...0), etc.) and the plane x + y + ... + z = k. We could then try to estimate the area of that "plane" with its corners clipped off by the limits at c(i) along the ith coordinate axis. Then we could consider rotating this diagonal plane (and all the points of intersection of the plane with the c(i)=constant truncating planes), and then computing the enclosed "area".

Yet another approach is to imagine the possibilities as a solid "brick" with dimensions [c(1)+1], [c(2)+1], ...etc. The sum of all the N(k) values equals the volume of this brick, and the individual values of N(k) are the volumes swept out by a diagonal plane as it emanates out from one corner of the brick. The values of N(k) start out small in the corner, then get bigger as the plane sweeps through the middle of the brick, and then get small again as the plane sweeps through the diagonally opposite corner. The values of N(k) will change in a uniform way except when the plane passes through a vertex of the brick. Also, by inclusion-exclusion we can predict how the derivative of N(k) vs k will change at each vertex. On this basis, we can formulate an exact solution as follows.

Let N(k) denote the number of ways of distributing k identical items into m containers with capacities c(1), c(2),.. c(m). Then

where s(t,j) is the jth sum of t "capacity-plus-1's".

For example, suppose we have m = 5 containers with capacities 3, 6, 9, 12, and 15. The "capacity-plus-1s" are therefore 4, 7, 10, 13, and 16. Our formula for N(k) begins with t = 0, and there is only one sum of zero capacity-plus-1s, namely 0, so we have s(0,1) = 0. Thus the outer summation for t = 0 contributes +C[5+k-1,4]. (Note that we define the binomial coefficient C[i,j] to be zero for all i < j.)

With t = 1 we will have 5 (=C[5,1]) negative terms, corresponding to the five possible sums of exactly 1 c-plus-1s:

With t = 2 we will have 10 (=C[5,2]) positive terms, corresponding to the ten possible sums of exactly 2 c-plus-1s. For example, the first of these ten terms is +C[k–7,4].

Continuing in this way the complete formula will have 32 (=2^m) terms, giving the exact value of N(k) for any k. Of course, we won't necessarily need all of these terms to evaluate N(k) for particular values of k. In fact, we never need more than half of these terms, because we only need to include terms with s[t,j] less than or equal to k, and if k exceeds half of the total capacity c of all the containers, we can just evaluate c–k instead.

To illustrate, suppose we want to evaluate N(31) for the above set of five containers. By symmetry this is the same as N(14), so we only need to use the terms

By the way, in the special case where all the capacities c[i] are equal to a single constant R, it's clear that the C[m,t] elements of the inner summation in equation (1) for a given t are all equal to C[m+k–s(t,j)–1,m–1] where each s(t,j) equals simply t(R+1). Therefore, in this special case equation (5) reduces as one would expect to the well-known result

Return to MathPages Main Menu