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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.