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!water!watdaisy!gjerawlins
From: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Newsgroups: net.puzzle
Subject: Re: Balls and buckets combinatorics problem
Message-ID: <7293@watdaisy.UUCP>
Date: Sun, 9-Jun-85 22:27:33 EDT
Article-I.D.: watdaisy.7293
Posted: Sun Jun  9 22:27:33 1985
Date-Received: Mon, 10-Jun-85 22:11:31 EDT
Reply-To: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Distribution: net
Organization: U of Waterloo, Ontario
Lines: 34

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