Thanks to all the people who sent advice about this problem.
There is a nice recursive solution. We have, writing p(k,r) for p(k|r,N)
p(1,r) = 1/N**(r-1)
p(r,r-1) = 0
p(k,r) = p(k,r-1)*k/N + p(k-1,r-1)*(N-(k-1))/N for 2 <= k <= min{r,N}.
Of course, getting the solution to the difference equation is more
complicated!
Mike Wiper
> Dear all.
>
> I have a problem related to the birthday problem.
> A bag contains N balls numbered 1 to N. We sample r balls with
> replacement. What is the probability P(k|r,N) that we
> find exactly k differently numbered balls in the sample of r picks
> where k = 1, ..., min{N,r}.
> (The birthday problem probability is 1 - P(k = r) when N=365.)
>
> If anyone knows the solution to this one or knows of any good
> reference to a solution, I would be glad to hear from you.
>
> Thanks,
>
> Mike Wiper
>
