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. Instead of taking 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 c SUM N(k) = [c(1)+1][c(2)+1]...[c(m)+1] (1) k=0 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: 1 5 15 33 59 90 120 142 150 142 120 90 59 33 15 5 1 (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 (3+1)(2+1)(5+1)(4+1)(2+1) = 1080 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 ______ (c/2 + 1) / 2 pi z exp(-(z^2)/2) = ----------------- (2) A for z, and set s = (c/2 + 1)/z. Then the individual values of N(k) are given approximately by A/s /-((k - c/2)/s)^2\ N(k) ~ ------------ exp( ---------------- ) (3) (2 pi)^(1/2) \ 2 / 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 /-((k-8)/2.84)^2 \ N(k) ~ (151.7) exp( --------------- ) (4) \ 2 / 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 only applies to relatively small perturbations around the condition of uniform capacities. One approach, might 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. This is how I originally looked at the problem, and I tried to see how to estimate the area of that "plane" with its corners clipped off by the limits at c(i) along the ith coordinate axis. I thought about 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". But now I'm picturing it slightly differently, 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 nice thing about this image is that you can see 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 you can predict how the derivative of N(k) vs k will change at each vertex. On this basis, I think we can formulate an exact solution. 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 /m\ m \t/ / m+k-s(t,j)-1 \ N(k) = SUM (-1)^t SUM ( ) (1) t=0 j=1 \ m-1 / 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 SUM 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: - C[k,4] - C[k-3,4] - C[k-6,4] - C[k-9,4] - C[k-12,4] 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 N(14) = C[18,4]-C[14,4]-C[11,4]-C[8,4]-C[5,4]+C[7,4]+C[4,4] = 3060 - 1001 - 330 - 70 - 5 + 35 + 1 = 1690 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 (1) reduces as one would expect to the well known result m /m\ / m+k-t(R+1)-1 \ N(k) = SUM (-1)^t ( )( ) t=0 \t/ \ m-1 /

Return to MathPages Main Menu