I understand that if you wanted to compute the probability of rolling a specific three of a kind or more (getting three or more $1$s for example) then you would just calculate $$\sum_{k=0}^3(5^k){6\choose 6-k}\over 6^6$$ but I am not so sure how you would go about calculating the probability for any value to appear three or more times in a roll of six dice. Simply multiplying the total outcomes for obtaining three or more of a specific value is obviously not correct because you would count outcomes such as $(1,1,1,2,2,2)$ once for getting three $1$s and again for getting three $2$s.
Is there a general formula or method one can use to obtain the answer to not only the dice scenario, but any scenario where $P(X\ge x)$ for $X$ denoting the maximum amount of times any value appears in a string of $m$ values generated from $n$ different values?
Thanks in advance, and sorry if my wording is bad. I'm still not entirely sure of the best way to word the last part.
Best Answer
There's more than one way. What's best depends on the relative sizes of $m$, $n$, and $x$.
First, we can go "forward" - enumerate all ways to have three or more of a kind, all ways to have three or more of two kinds, and so on, then run inclusion-exclusion. As noted in the comment by @JMoravitz, this works pretty well for your example of $x=3,m=n=6$.
For a particular $k$, there are $\binom{6}{3}\cdot (6-1)^3$ ways to have three of $k$, $\binom{6}{4}\cdot (6-1)^2$ ways to have four of $k$, $\binom{6}{5}\cdot (6-1)$ ways to have five of $k$, and $\binom{6}{6}$ ways to have six of $k$. Multiply by $6$ to get a total of $$6\left(\binom{6}{3}\cdot 5^3+\binom{6}{4}\cdot 5^2+\binom{6}{5}\cdot 5^1+\binom{6}{6}\right)$$ ways. But, of course, this is an overcount. We can have three each of two different kinds, in $\binom{6}{3}$ ways to choose which three are the "first" kind and $\binom{6}{2}$ pairs of kinds. These were counted twice by the preceding, so we subtract them off to get $$6\left(\binom{6}{3}\cdot 5^3+\binom{6}{4}\cdot 5^2+\binom{6}{5}\cdot 5^1+\binom{6}{6}\right)-\binom{6}{2}\cdot\binom{6}{3}$$ $$= 6(20\cdot 125+15\cdot 25+6\cdot 5+1)-15\cdot 20 = 17136$$ ways. Divide by $6^6=46656$ for the probability (about $0.367$).
Of course, as we increase $m$ for fixed $n$ and $x$, eventually we reach a point where that $x$ of a kind is certain (Pigeonhole principle). If we're close to that point, the forward count will be horrible - but there's an alternative. We can count the ways to avoid any instances of $x$ of a kind, and subtract the resulting probability from $1$. I'll demonstrate this backward count for the same example:
To avoid three of a kind, we must have between zero and 2 of each of the six kinds. I'll enumerate the possible ways to split $6$ into a sum of six terms each between zero and $2$: $2+2+2+0+0+0$, $2+2+1+1+0+0$, $2+1+1+1+1+0$, $1+1+1+1+1+1$.
For $2+2+2+0+0+0$, we have $\binom{6}{3}$ ways to choose which three numbers on the die show up, then $\binom{6}{2,2,2}=\binom{6}{2}\binom{4}{2}$ ways to choose which rolls each number gets.
For $2+2+1+1+0+0$, we have $\binom{6}{2,2,2}$ ways to choose which numbers are represented to each level, then $\binom{6}{2,2,1,1}$ ways to choose the rolls.
For $2+1+1+1+1+0$, we have $\binom{6}{1,4,1}$ ways to choose the numbers and $\binom{6}{2,1,1,1,1}$ ways to choose the rolls.
For $1+1+1+1+1+1$, we have one way to choose the numbers and $\binom{6}{1,1,1,1,1,1}=6!$ ways to choose the rolls.
Summing those up, that's $$20\cdot 90+90\cdot 180+30\cdot 360+1\cdot 720 = 29520$$ ways to avoid three of a kind. The probability we seek is $$1-\frac{29520}{46656}=\frac{17136}{46656}\approx 0.367$$ This backwards count never really goes too bad - the example here is a "worst" case of having the most possible ways to split $m$ - but it's particularly efficient when $m$ is close to $n(x-1)$, and it's instant when we're in the case $m > n(x-1)$ and at least one instance of $x$ of a kind is certain.