wws@whuxlm.UUCP (Stoll W William) (06/08/85)
Given N balls and B buckets, how many ways can the balls be distributed among the buckets such that it is possible to find a bucket with at least K balls in it? (K > 0, N >= K, B > 0) This problem was posed by a friend with values K == 65, N == 5000, and B == 100. I have a text which answers the question "ways which result in E empty buckets", but I can't apply it to the above. Help is appreciated! Bill Stoll, ..!whuxlm!wws
gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (06/10/85)
In article <779@whuxlm.UUCP> wws@whuxlm.UUCP (Stoll W William) writes: >Given N balls and B buckets, how many ways can the balls be distributed >among the buckets such that it is possible to find a bucket with at >least K balls in it? (K > 0, N >= K, B > 0) > >Bill Stoll, ..!whuxlm!wws The solution to this is the sum of all the partitions of i for 0 <= i <= N-K where the number of parts of each partition is less than or equal to B. This is easiest to see if we imagine all possible ways in which the condition could be satisfied assuming that we have infinitely many buckets (or at least as many buckets as balls). If K = N-0 then there is only one way to satisfy the condition, namely if all N balls are in one bucket (assuming all balls and buckets indistinguishable). If K = N-1 then there are exactly two ways to satisfy the condition, namely either all balls are in one of the buckets or N-1 are in one and one in some other. If K = N-2 then we may satisfy the condition in four ways. Either we place all N balls in one bucket (1 way), or we place N-1 in one and 1 in another (1 way), or we place N-2 in one and 2 in another, or, finally, if we place N-2 in one and one each in two others. And so on. It is easy to prove that if K = N-j (j>=0) then there are exactly $ sum over i from 0 to j of P(i) $ possible ways to satisy the condition. This is not a number to be trifled with since P(i) is of the order of (e^(sqrt(i)))/i, so the sum is quite large. When we have less buckets than balls this means that some of these partitions are impossible, in fact we only need sum those partitions which have no more than B parts. -- Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins
mvramakrishn@watdaisy.UUCP (Rama) (06/14/85)
> > Given N balls and B buckets, how many ways can the balls be distributed > among the buckets such that it is possible to find a bucket with at > least K balls in it? (K > 0, N >= K, B > 0) > > This problem was posed by a friend with values K == 65, N == 5000, > and B == 100. I have a text which answers the question "ways which > result in E empty buckets", but I can't apply it to the above. > Help is appreciated! > > Bill Stoll, ..!whuxlm!wws > A more interesting and difficult problem is Given N balls M buckets Each bucket has a capacity to hold atmost B balls. In how many ways can the balls be distributed among the buckets? { Let it be denoted by F(N,M,B) } [ Ofcourse N <= M*B, Buckets are numbered (distinguishable) and balls are not.] ------------------------------------ It is more clear if the question is posed as follows. If each of the N balls are tossed into the buckets so that for any ball the probability that it lands in a particular bucket is (1/M), what is the probability P(N,M,B), that none of the bucket overflows(overflows = receives more than B balls)? P(N,M,B) = F(N,M,B) / (M**N) Note: Approximate evaluation (quite accurate for large M) is easy But, accurate evaluation is more difficult. Consider, N = 500, B = 30, M = 25. ------------------------------------ ....Rama..... UUCP: {decvax,utzoo,ihnp4,allegra,clyde}!watmath!watdaisy!mvramakrishn CSNET: mvramakrishn%watdaisy@waterloo.csnet ARPA: mvramakrishn%watdaisy%waterloo@csnet-relay.arpa
wws@whuxlm.UUCP (Stoll W William) (06/24/85)
> > > > Given N balls and B buckets, how many ways can the balls be distributed > > among the buckets such that it is possible to find a bucket with at > > least K balls in it? (K > 0, N >= K, B > 0) > > > > This problem was posed by a friend with values K == 65, N == 5000, > > and B == 100. I have a text which answers the question "ways which > > result in E empty buckets", but I can't apply it to the above. > > Help is appreciated! > > > > Bill Stoll, ..!whuxlm!wws > > > A more interesting and difficult problem is > Given N balls > M buckets > Each bucket has a capacity to hold atmost B balls. > > In how many ways can the balls be distributed among the buckets? > { Let it be denoted by F(N,M,B) } > > [ Ofcourse N <= M*B, > Buckets are numbered (distinguishable) and balls are not.] > ------------------------------------ > Ok, two questions: 1) What is F(N,M,B)? I am still stuck. If I could solve this, you are right, I could solve my original problem. 2) How is this problem more interesting than the original? :-) Thanks for responding, Bill Stoll, ..!whuxlm!wws