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!
 A: 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 $$
A: 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. 
A: You can avoid the over-counting using the inclusion-exclusion principle.
