What are the odds of at least k same outcomes in n independent trials, each with x equally likely outcomes?

Some initial thoughts...

Your question is related to--but not exactly the same as--a flavor of combinatorics questions called "stars and bars." The reason it's not the same is that you want the probability of a specific set of outcomes, whereas stars and bars is simply interested in counting the number of such outcomes.

Let's pretend like you cared about counting instead of probability for a second. Essentially, you have n balls and x bins, and your question is "how many ways can I assign the n balls to x bins such that there are at least k balls in at least one bin."

Ignoring the restriction, it's a straightforward calculation, where each unique outcome can be depicted by a unique sequence of stars and bars where stars represent balls and bars separate the bins. You need x-1 bars to separate x bins. For example, let's say n = 3 and x = 4, the outcome:

*||**|

represents the outcome where there is 1 ball in bin 1, 0 balls in bin 2, 2 balls in bin 3 and 0 balls in bin 4. The total number of outcomes would be the total number of ways to choose n spaces to be stars among n + x - 1 spaces.$${n+x-1 \choose n}$$
With the restriction that at least 1 bin needs at least k balls, well, things get really hard really fast. A sensible approach may be to try to count the number of ways in which the condition is not met and subtract that from the total number of ways where we disregard the condition. The number of ways where the condition is not met is equal to the number of ways to put n balls in x bins such that no bin has more than k-1 balls.

The top answer in this stack exchange post gives a nice answer as to how to calculate this number:

https://math.stackexchange.com/questions/553960/extended-stars-and-bars-problemwhere-the-upper-limit-of-the-variable-is-bounded. Note that they use n where you use x, they use r where you use k, and they use N where you use n.

The issue at hand now is that simply counting the number of ways something can happen is not enough to answer your question. This is because each 'outcome' that we're counting is not equally likely. We would also need to calculate the probability of each case. Which, for each individual case is not hard. Lets use your Yahtzee example:

For "at least one three-of-a-kind," one example of a satisfactory outcome would be three 1's and two 5's. The probability of getting exactly three 1's and two 5's would be $${5 \choose 3}{2 \choose 2}\frac{1}{6^{5}}$$

Then, I was thinking about this problem in bed and realized that what we're looking for is the distribution of the maximum of a multinomial distribution. Let's say X is a multinomial random variable with 6 equally likely outcomes and 5 independent trials. X is essentially a vector that counts how many of each outcome was observed. Then let Y = max(X). In your Yahtzee example, you'd be looking for: $$P(Y \geq 3)$$I did some googling to see if some research has been done in the distribution of the maximum of a multinomial distribution.

https://www.jstor.org/stable/2347220 gives an algorithmic answer, but honestly, I wouldn't know how to translate the 1970's pseudocode into a modern programming language. But I'm sure there are people out there who could. Interestingly, though, this paper also cites several approximations from previous work, which may be interesting to look into.

https://www.stat.purdue.edu/%7Edasgupta/mult.pdf provides a useful approximation if you want to say something like "95% of the time, the max is at most x." Which, again, is related to what you want but not exactly what you want.

https://royalsocietypublishing.org/doi/10.1098/rsos.190198 provides a nice history of various approximate solutions over time, as well as an approach to an exact answer. Section 4.1 gives a (quite complicated) procedure to arrive at the exact answer you're looking for.

https://repository.tudelft.nl/islandora/object/uuid:aa9c02f9-71e9-4ba4-840d-596aa0e2341a/datastream/OBJ/download is a very thorough deep-dive into methods and applications, several of which we’ve already seen.

Hopefully I’ve provided enough resources and search-terms for you to get started. Clearly this is an absolutely massive topic that, quite literally, masters theses have been written on. Many clever people have been able to come up with clever parametric approximations, as well as some algorithmic exact solutions. But no one has been able to come up with a neat closed-form solution that you can simply plug your numbers into.