Re: help: probability of dropping k items into N buckets

From: Lars Luthman (unspammable_at_inter.net)
Date: 10/06/04 

Date: Wed, 06 Oct 2004 15:11:45 +0200

On Fri, 2004-09-24 at 15:17 -0700, Bo Hong wrote:
> Hello,
>
> Suppose there are k items and N buckets. k may be less than, equal
> to, or larger than N.
>
> Each of the k items are dropped into one bucket. The droppings of
> the k items are independent. Item i (1<=i<=k) has probability 1/N to be
> dropped into any of the buckets.
>
> What is the probability that at least one bucket has exactly one item?
>
> For example, suppose we have 4 items and 2 buckets. Let (a,b)
> denote the dropping of a items in bucket 1, and b items in bucket 2.
> Then (1,3) statisfies the condition that 'at least one bucket has
> exactly one item'. (2,2) does not satisfy the condition since none of
> the bucket has exactly one item.

Hint: Let F(a,b) be the number of ways to drop a items in b buckets, and
let G(a,b) be the number of ways to drop a items in b buckets such that
at least one bucket has exactly one item. Then G(a,b) = b*F(a-1,b-1) and
the wanted probability is G(a,b)/F(a,b) = a*F(a-1,b-1)/F(a,b). F(a,b)
should be easy to calculate. 

-- 
Lars Luthman
PGP key:     http://www.d.kth.se/~d00-llu/pgp_key.php
Fingerprint: FCA7 C790 19B9 322D EB7A  E1B3 4371 4650 04C7 7E2E