## 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.

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.

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      /

```