Odds of rolling doubles or triples given N 6-sided dice

Question

Over the holidays I played a dice game where each player had 3 to 7 d6 to roll each turn. The game gave certain advantages to doubles and triples. I wanted to know the odds of rolling doubles or triples given N dice to understand the importance of "upgrading" to more dice.

My question is really about how to reason about such problems: It's easy to see that the odds of rolling doubles with 2 d6 are 1/6 (first die can be anything, and 1/6 of the time the second will match). It's also easy to see that with 7 dice the odds are 1.0 (6 dice could be 1..6, but the 7th must match one of them). The middle cases are fuzzier to me.

I ended up writing a program to enumerate all of the possibilities (even 6^7 is only 279,936 cases to evaluate) because that was the only way I felt I could verify any closed formula I came up with. This also enabled me to distinguish cases of multiple doubles (or triples). I would like to know how to derive closed forms and how to validate such solutions without brute-force simulation.

Answer 1

You are looking at a much more manageable version of the famous birthday problem, which has 365 choices for each "die". The link describes the solution as well. In short, the trick for counting duplicates is to rather counting the cases without a duplicate - that is much simpler.

Answer 2

You have posed the kind of combinatorics question that profs will ask you as an undergrad.

Let's reduce the problem to doubles of two dice. Instead of asking about doubles, let's ask how not to roll doubles. There are 6 ways to roll the first die and 5 ways (excluding the first die's roll) to roll the second die. Because we are not rolling doubles, we could pair a 1 like this:

1 2
1 3
1 4
1 5
1 6

You could continue this pattern for 6 x 5 or 30 non-doubles. There are 6 * 6 = 36 ways to roll a pair of dice, so 36 - (6 * 5) gives you 6 ways to roll doubles.

That was trivial, but let's build up to 3 dice.

How many ways are there to not roll 3 dice that are the same? The answer is 6 * 5 * 4 = 120, because there are 6 ways to roll the first die, 5 ways to roll the second (and not duplicate the first), and 4 ways to roll the third die (and not duplicate the first or the second).

Here are the ways to not roll a double or triple with three dice, when the first die is a 1.

1   2   3
1   2   4
1   2   5
1   2   6
1   3   2
1   3   4
1   3   5
1   3   6
1   4   2
1   4   3
1   4   5
1   4   6
1   5   2
1   5   3
1   5   4
1   5   6
1   6   2
1   6   3
1   6   4
1   6   5

There are 6 * 6 * 6 = 216 ways to roll three dice, and 6 * 5 * 4 ways to roll non-duplicates, so there are 216 - 120 = 96 ways to roll doubles OR triples.

Answer 3

You're really asking for instruction in combinatorics, which is a vast field. For this particular problem, a good method, if somewhat abstract, is to use generating functions. The probability generating function (pgf) for a d$n$, where $n = 1, 2, \ldots$, is obtained by averaging $n$ variables. Their names don't matter, so let's call them $x_1, x_2, \ldots, x_n$. The pgf for $k$ rolls is just the $k^{\text{th}}$ power of the pgf for 1 roll. So, if you expand

$$\left(\frac{x_1 + x_2 + \cdots + x_n}{n}\right)^k$$

you can read the answer to any question by inspecting the coefficients.

For example, to find the probability of rolling a full house (three of one number, two of another) in Yahtzee ($n=6, k=5$) look at all the terms in $((x_1 + \cdots + x_6)/6)^5$ involving a third power and a second power. There are 15 of them, each with the coefficient 5/3888, and each counts distinctly different outcomes, so the chance of a full house is the sum of these chances, equal to 15*5/3888.

It's straightforward to write code that multiplies and adds polynomials of this sort. The number of calculations for seven rolls of your d6 is just a few thousand, far smaller than the hundreds of thousands needed to enumerate and tally all possible combinations.

Mathematical analysis of generating functions often gives closed-form formulas for the coefficients. Many examples are available; you can check some of them out on the math site.