Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watnot!watdaisy!mvramakrishn
From: mvramakrishn@watdaisy.UUCP (Rama)
Newsgroups: net.puzzle
Subject: Re: Balls and buckets combinatorics problem
Message-ID: <7306@watdaisy.UUCP>
Date: Thu, 13-Jun-85 17:27:37 EDT
Article-I.D.: watdaisy.7306
Posted: Thu Jun 13 17:27:37 1985
Date-Received: Fri, 14-Jun-85 00:07:20 EDT
References: <779@whuxlm.UUCP>
Distribution: net
Organization: U of Waterloo, Ontario
Lines: 41

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