4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it just me or is their closed form incorrect? Seems like their n changes meaning to 365-n in the final step. $\endgroup$ – Ben Jackson Jan 3 '11 at 23:35
  • $\begingroup$ I don't think so. Just write out the definition of the binomial coefficient, and you'll see that the equality works. Note that ${n\choose k} = {n\choose {n-k}}$ $\endgroup$ – Aniko Jan 4 '11 at 13:54
  • 1
    $\begingroup$ Yes, "more manageable" for the question of doubles, assuming only a d6 and not a d365. For triples, etc., you need more powerful methods. $\endgroup$ – whuber Jan 4 '11 at 22:04
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How does it help to suggest that this is an "undergrad" question? Is that relevant to the answer? Does it suggest ways to search for an answer on the Web? I hope this remark wasn't intended to belittle the questioner. $\endgroup$ – whuber Jan 4 '11 at 16:29
  • $\begingroup$ @whuber, no the remark was made with a smile and happy memory of Prof. Bentley's combinatorics class. No disparagement was intended. $\endgroup$ – rajah9 Jan 4 '11 at 20:21
  • 1
    $\begingroup$ I am very glad to read your clarification. It's easy to misunderstand parenthetical comments when they are only written and not spoken. $\endgroup$ – whuber Jan 4 '11 at 20:24
  • $\begingroup$ Aren't there actually 6 ways to roll the second dice and 5 ways to roll the third in order to avoid a triple? This does not answer the stated question, "How many ways are there to not roll 3 dice that are the same?" But rather answers how many ways are there to avoid both triples and any doubles. $\endgroup$ – John May 3 '15 at 0:31
  • $\begingroup$ @John, I respectfully disagree that the OP stated a question, "How many ways are there to not roll 3 dice that are the same?" I do not see the quoted words in the question. Four years ago (!), I answered the question implicit in the heading: "Odds of rolling doubles or triples given N 6-sided dice." $\endgroup$ – rajah9 May 4 '15 at 13:56
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I just want to comment that anyone familiar with the Binomial theorem and multinomial coefficients can easily use this generating function to write down a closed-form formula for any specified pattern (a partition of the number of dice). It is a product of two multinomial coefficients. The point of this response is that you can go pretty far without any such knowledge, solely by exploiting generating functions. $\endgroup$ – whuber Jan 4 '11 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.