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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search