# Probability of getting exactly $k$ of a kind in $n$ rolls of $m$-sided dice, where $k\leq n/2$

This question was inspired by this question dealing with finding the probability of rolling a $7$ of a kind with $10$ dice.

Is there a general method for finding the chance of rolling a $k$ of a kind with $n$ $m$-sided dice when $k\leq n/2$? When $k>n/2$ the probability is found relatively easily with the Bernoulli distribution, but when $k\leq n/2$ there's the possibility that one may roll a second, or third, etc., $k$ of a kind with the other $n-k$ di(c)e. I don't see a clear way around this possible over counting.

Thanks!

-
You have to define what you mean here, I think. Suppose you want exactly three of a kind in ten rolls. Presumably you would reject a result of three twos and four fives, say. Would you also reject a result of three twos and three fives? – TonyK Jan 12 '11 at 13:56
@Tony K, I'm sorry if I was unclear. My definition of getting exactly $k$ of a kind, just means that there should be at least one $k$ of a kind of some sort. So yes, if I were looking for a three of a kind, I would consider three twos and four fives a $3$ of a kind of twos, but of course not a three of a kind of fives. Similarly, I would accept three twos and three fives as both a three of a kind of twos and a three of a kind of fives. – yunone Jan 12 '11 at 14:50

Let $A_i$ be the event that we obtain exactly $k$ $i$'s (assuming that the dice are labeled $1,2,3,\ldots,m$ on their sides). Now inclusion-exclusion gives

$$P(A_1 \cup A_2 \cup \ldots \cup A_m) = \sum P(A_i) - \sum P( A_i \cap A_j) + \sum P(A_i \cap A_j \cap A_k ) - \cdots$$

where the summations range over distinct $i,j,k,\ldots .$

We have

$$P(A_i) = { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k}$$

and

$$P(A_i \cap A_j) = { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} \cdot { n-k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-2k}$$

and

$$P(A_i \cap A_j \cap A_k)$$ $$= { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k} \cdot { n-k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-2k} \cdot { n-2k \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-3k}$$

and so on.

Simplifying these expressions, the probability that we get exactly $k$ of a number is given by

$$P(A_1 \cup A_2 \cup \ldots \cup A_m)$$

$$= { m \choose 1 } { n \choose k} \left( \frac{1}{m} \right)^k \left( 1 - \frac{1}{m} \right)^{n-k}$$

$$- { m \choose 2 } { n \choose k} { n-k \choose k} \left( \frac{1}{m} \right)^{2k} \left( 1 - \frac{1}{m} \right)^{2n-3k}$$

$$+ { m \choose 3} { n \choose k} { n-k \choose k} { n-2k \choose k} \left( \frac{1}{m} \right)^{3k} \left( 1 - \frac{1}{m} \right)^{3n-6k} - \cdots$$

-
This is based on my interpretation that the poster if after the probability that we get exactly $k$ of one number when $n$ $m$-sided dice are rolled. – Derek Jennings Jan 12 '11 at 14:02
Thanks for this answer, Derek. I think this may be what I'm looking for. Based on a comment by Tony K, I'm afraid my definition of a $k$ of a kind may have been confusing. If I understand you correctly, if a roll was given where there were say $k$ twos and $k$ fives, you would accept this as both a $k$ of a kind of twos, as well as a $k$ of kind of fives, as opposed to outright rejecting it as either? And then of course your calculation uses IE to not overcount such a situation? – yunone Jan 12 '11 at 14:56
@yunone: Yes, I would accept exactly $k$ twos and exactly $k$ fives appearing in the roll of the $n$ dice and, as you say, use IE not to overcount. – Derek Jennings Jan 12 '11 at 18:05
@yunone: I've just spotted your comment to Tony K in the question and I am happy that my interpretation of the question agrees with the question you want to ask. – Derek Jennings Jan 12 '11 at 18:22

You can avoid the over-counting using the inclusion-exclusion principle.

-

Isn't this pretty straightforward? You pick the side that you want there are $m$ ways to do this. Then you are rolling $n$ dice and you want k dice to be a certain side of which there is a $(1/m)^k$ chance (if in a row) and then $((m-1)/m)^{(n-k)}$ for the remaining dice. You also need to account for different orders so you have $n$ choose $k$ choices for your dice on side k and these will determine the positions of your non-k sided dice. Putting everything together we get

$m \binom{n}{k} \frac{1}{m^k}\left(\frac{m-1}{m}\right)^{n-k}.$

Whoops, wasn't paying attention when I wrote this. Then we want to know the probability that none of the remaining (n-k) dice are a k of a kind. So we need to subtract away the probability that there exists a k of a kind in the spare dice. First we have (n-k) choose k pairs to examine and the probability that all k are not the same so once again we have to pick a side, but note that we can only pick (m-1) sides because we've already ensured that they are not one of the sides. Finally we get

$m \binom{n}{k} \frac{1}{m^k}\left(\frac{m-1}{m}\right)^{n-k}-(m-1)\binom{n-k}{k}\frac{1}{(m-1)^k}.$

I believe this is right, it certainly holds for the k>n/2 case.

-
You are heading in the right direction of the inclusion-exclusion principle, but need to keep going in case k<n/3 and there are three sets of k and so on. – Ross Millikan Jan 12 '11 at 13:57
Thank you for this response, Jacob. – yunone Jan 12 '11 at 14:57
It's definitely not correct though, it makes sense on a superficial level, but it's not right. I wrote up a quick program to run the simulation and also calculate my formula and it's not correct. Jennings answer is right I'm fairly sure though. – JSchlather Jan 12 '11 at 15:05