Occupancy Problem

Date: 08/06/2001 at 20:38:16
From: Mauricio Gonzalez
Subject: Occupancy problem with n bins and  m balls - new twist

Hello,

I'm trying to solve the following problem:

Given n bins and m (indistinguishable) balls, how many arrangements 
are possible such that no bin has greater than r balls?

We note that r cannot be arbitrarily small. In fact, if r < (m/n) 
(rounded up if necessary to next higher integer value), then the 
condition of no bin having greater than r balls cannot be satisfied, 
since the remaining balls have to fit among the n bins somehow 
(intuitively we can think of pouring a jug of water into several 
glasses, but ensuring no water is left in the jug).

I've looked at the standard occupancy problems in the archives, but am 
still stumped.

Thanks.
Mauricio.

Date: 08/07/2001 at 09:39:35
From: Doctor Anthony
Subject: Re: Occupancy problem with n bins and  m balls - new twist

You need to do this in two stages. The second stage involves the 
inclusion-exclusion principle to remove the number of arrangements 
with more than r-1 balls in a bin. The method is best illustrated 
using actual numbers. 

As an example, in how many ways can 20 balls be distributed amongst 10 
urns such that no urn contains more than 5 balls?

We start by finding the number of unrestricted ways that 20 balls can 
be distributed in 10 urns. We can illustrate the problem as follows:

  |****|***|    |***|******|   | ** | * |   | * |

This represents occupancy 4,3,0,3,6,0,2,1,0,1

The total number of possibilities is the same as the number of 
distinct arrangements of 20 *'s and 9 |'s.  This is given by

       29!
    -------- = C(29,20) = C(29,9)
     20! 9!

This is the same as the number of integer solutions of the equation

    x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 = 20

Now if x1 is greater than 5 we put y1 = x-6, y2 = x2, y3 = x3, etc., 
and must find the number of integer solutions of

    y1 + y2 + y3 + ...... + y10 = 14

By same reasoning as before this is   C(14+10-1,9) = C(23,9)

The same would be true if x2 > 5 or x3 > 5, and there are 10 such 
results with one of the x's greater than 5.

If both x1 and x2 are greater than 5 we put y1 = x1-6, y2 = x2-6, 
y3 = x3, y4 = x4, etc., and now we require number of solutions of 

   y1 + y2 + y3 + ..... + y10 = 8

And again the number of solutions is C(8+10-1,9) = C(17,9)

There are C(10,2) = 45 pairings of x's with both greater than 5.

If x1, x2, and x3 are greater than 5, we put y1 = x1-6, y2 = x2-6, 
y3 = x3-6, y4 = x4, y5 = x5, etc., and we require the number of 
solutions of

   y1 + y2 + y3 + ..... + y10 = 2

The number of solutions is C(2+10-1,9) = C(11,9)

There are C(10,3) = 120 triples with each of the x's greater than 5.

Clearly we cannot have 4 of the x's greater than 5, and so we are now 
in a position to apply the inclusion-exclusion principle for 
calculating the number of solutions such that none of the x's is 
greater than 5.

Number of solutions 

     = C(29,9) - 10.C(23,9) + 45.C(17,9) - 120.C(11,9)

     = 2930455

Once the method has been established, a general formula would look 
like this. Suppose that there are m balls, n urns and r-1 is the 
maximum number in any urn.

Number of arrangements

 = C(m+n-1,n-1) - C(n,1).C(m+n-1-r,n-1) + C(n,2).C(m+n-1-2r,n-1) -

and continue in this fashion until you run out of terms with the 
number of urns containing more than r-1 balls exceeding the balls 
available.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/