Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Occupancy Problem

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


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.


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

    -------- = 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 

- Doctor Anthony, The Math Forum
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994-2013 The Math Forum