Chance of selecting a duplicate?

When you select things at random repeatedly (with replacement or whatever) out of a field of N possible things, how do you calculate the probability that something has been chosen X times after Y choices were made? For example, if there are 64 DotA 2 heroes and I choose a random one 9 times, what's the chance that I get Skeleton King 5 of those times?

-
At least 5 or exactly 5? – Qiaochu Yuan Jan 4 '12 at 1:50
Both, I guess.. – Robert Fraser Jan 4 '12 at 1:52

This is the probability of getting $k$ successes in $n$ Bernoulli trials. If exactly five, you multiply:

• the probability of, in a game, getting Skeleton King ($1/64$); done five times
• the probability of, in a game, not Skeleton King ($63/64$); done four times
• the number of distinct rearrangements of these 9 events, which is ${{9}\choose{5}}$ – intuitively, this is the number of ways to "choose" the 5 games out of 9 where you rolled Skeleton King.

Rolling this all up, the formula is (Wolfram Alpha link):

$${{9}\choose{5}} \left(\frac{1}{64}\right)^5\left(\frac{63}{64}\right)^4 \approx 1.1 \times 10^{-7}.$$

For the probability that you rolled Skeleton King at least five times, you can use the same formula but sum up all the possibilities past 5 up through 9 (Wolfram Alpha link):

$$\sum_{k=5}^9 {{9}\choose{k}}\left(\frac{1}{64}\right)^k \left(\frac{63}{64}\right)^{9-k} \approx 1.1 \times 10^{-7}.$$

Your explanation of why ${9 \choose 5}$ occurs is a little incomplete. The 5 things you're choosing are the 5 slots out of 9 where Skeleton King occurs. Also, shouldn't the resulting number be less than $1$? – Qiaochu Yuan Jan 4 '12 at 2:01