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.

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      /