# Rolling dice such that they add up to 13 — is there a more elegant way to solve this type of problem?

Here is the problem:

There are $6^3$ possible outcomes to rolling a die $3$ times. Out of these, how many yield a total of (exactly) $13$ dots?

My solution would be absolutely impractical for problems involving $4$ rolls of the die. And at higher numbers it would be downright impossible without brute-forcing it with a computer.

Is there a more elegant way to solve this type of problem?

My solution:

First we find all sets $\{a, b, c\}$ such that $a + b + c = 13; \; a, b, c \le 6$:

$\{1, 6, 6\}$

$\{2, 5, 6\}$

$\{3, 4, 6\}, \{3, 5, 5\}$

$\{4, 4, 5\}$

The total number of sets that fit these criteria is $5$. If $a \not= b \not= c$, then there exist $3!$ unique permutations of $\{a, b, c\}$. If $a = b \not= c$, then there exist $3$ unique permutations of $\{a, b, c\}$. -- There cannot be a set such that $a = b = c$.

There are $2$ sets of the first kind and $3$ of the second. It follow that the total number of triple die rolls that can fit the criteria is

\begin{equation*} 2 \cdot 3! + 3 \cdot 3 = 21 \end{equation*}

I can think of a second way to do it, which might be faster for slightly larger numbers... but essentially still comes down to brute force, not a method that can be generalized.

-
If you're going for elegant, I think the method from Fool's answer below is nice. Basically the computation is reduced to $\binom{12}{2} - 3 \cdot \binom{6}{2}$, with no brute-forcing, and no counting possibilities manually. Just some algebra. –  TMM Sep 28 '11 at 1:22
Could whoever downvoted this explain why? And also explain why they didn't post such an explanation here? –  Michael Hardy Sep 28 '11 at 11:06

## 5 Answers

Here's one approach which is suitable in various circumstances.

Consider the expression $(x+x^2+x^3+x^4+x^5+x^6)^3$. What is the coefficient of $x^{13}$ when you expand this out?

The expression can also be re-written as $\left(\frac{x(x^6-1)}{x-1}\right)^3$ to make it less unwieldy to work with. The coefficient of $x^k$ can be extracted by taking derivatives, for example.

This is a very useful tool which can be applied in much more general situations, as you may observe. For instance you could replace $1+x+\ldots+x^6$ by some other expression to represent dice with more faces, or dice with arbitrary faces, or dice with weights, etc.

-
Interesting! thanks. –  iDontKnowBetter Sep 27 '11 at 22:36
Including $1$ in the expression is equivalent to having seven sided dice with numbers $0$ through $6$. It doesn't hurt with $13$, but would with $11$, because you could afford a $0$. –  Ross Millikan Sep 27 '11 at 22:37
You're welcome. Note that I corrected my expression slightly to account for the fact that a die can't come up 0 - it doesn't change the answer in this case since 13 cannot be attained with 0's. –  Alon Amit Sep 27 '11 at 22:39

In this case it's easier to find the number of triples $(a,b,c)$ that sum up to 8. If $(a,b,c)$ are possible dice rolls that sum up to 8, then $(7-a,7-b,7-c)$ are also possible dice rolls and sum to 13. In general the number of ways to make $x$ and $21-x$ on three dice are the same. (With two dice, of course, the number of ways to make $x$ and $14-x$ are the same.)

Of course this is still brute force, but it's good to take advantage of symmetry -- for example, if you had been asked to find the number of outcomes giving $k$ dots for all of $k = 3, 4, \ldots, 18$, you could save yourself time by doing only half of them.

One way to do this for an arbitrary number of dice is as follows: let $N(d,s)$ be the number of ways to roll a sum of $s$ with $d$ dice. (So you're trying to find $N(3,13)$.) In order to get a sum of $s$ with $d$ dice, you must have a sum of between $s-6$ and $s-1$ on the first $d-1$ dice, and then roll the appropriate number on the final die. So you have $$N(d,s) = N(d-1, s-1) + N(d-1, s-2) + \cdots + N(d-1, s-6)$$ where we start with $N(0,0) = 1$ and $N(0,s) = 0$ for all other integers $s$. You can rearrange this to get $$N(d,s) = N(d, s-1) + N(d-1, s-1) - N(d-1, s-7)$$ and so you can compute each $N(d,s)$ with just one addition and one subtraction.

The generating-function method is actually the same as this, once you think about how polynomial multiplication works.

-
+1 for the method in your third paragraph, which is very easy to implement on a spreadsheet, especially if you have six blank rows at the top of your table. –  Henry Sep 27 '11 at 23:37

If I have understood your problem correctly then I guess we could use the stars and bars concept for a clever solution.

For example in your case,

$$x_1+x_2+x_3 = 13$$

Number of positive integer solution possible such that $x_i \ge 1$ is given by $\binom{12}{2}=66$.

Then set $x_1'=x_1+6$,so the equation reduces to: $$x_1'+x_2+x_3=7$$

which gives $15$ possible solution,using the same thing for $x_2$ and $x_3$ we would see that we have over-counted $3\times15$ solutions in our first calculation,hence subtracting $66-45=21$.

-
(+1) I was going to post a link to your earlier question but I see you already posted an answer using that method :) –  TMM Sep 28 '11 at 0:04

One way is generating functions: form $(x+x^2+x^3+x^4+x^5+x^6)^3$ and find the coefficient of $x^{13}$

-
Ah, the very last chapter in my combinatorics book is titled "generating functions", though I've not gotten there yet. Thanks. (This is from my current probability course, which starts with basic combinatorics). –  iDontKnowBetter Sep 27 '11 at 22:39
If you want to learn more about generating functions, you should take a look at Herb Wilf's book "generatingfunctionology", which can be found free online. (This is legal; Wilf has posted the book on his web page.) This book is probably best read after you know some combinatorics and some probability. –  Michael Lugo Sep 28 '11 at 1:03

If you throw the die a very large number of times, maybe there would be some difficulty in finding the exact number of ways in which a certain total can appear. But the central limit theorem from probability theory can give some reasonable approximations.

Say you throw the die 40 times. On average the sum is 140. There are $6^{40}$ possible outcomes. How many of those give a total in the closed interval $[135,150]$?

When you throw a die once, the variance of the probability distribution of the number of dots you see is $35/12$, so when you throw it 40 times, the variance is $40\cdot35/12= 10\cdot35/3$, and the standard deviation is therefore $\sqrt{350/3} = 10.801234497\ldots\ {}$. For this discrete distribution, "$\ge 135$" is the same as "$>134$" and "$\le 150$" is the same as "$<151$", so we do a continuity correction and look at the interval $(134.5,150.5)$. The number $134.5$ is $(134.5-140)/10.801234497\ldots)$ standard deviations above the mean, i.e. about $0.5092$ standard deviations below the mean, and $150.5$ is about $0.972$ standard deviations above the mean. Plugging these into the cumulative probability distribution function $\Phi$ of the normal distribution, we get a probability of about $\Phi(0.972)-\Phi(-0.5092)=0.529$.

So $0.529 \times 6^{40} \approx 7.074\times 10^{30}$ is approximately how many ways there are to get a sum in that interval.

-
Could whoever downvoted this explain why? And also explain why they didn't post such an explanation here? –  Michael Hardy Sep 28 '11 at 5:40
Don't sweat it. Random downvotes are more than balanced by random upvotes. –  TonyK Sep 28 '11 at 9:52
The concern is of course that it may not have been "random". Indeed, that is what one must presume. –  Michael Hardy Sep 28 '11 at 11:05
Yeah but still. –  TonyK Sep 28 '11 at 11:51
To suggest that "random downvotes are more than balanced by random upvotes" is to suggest that the concern here is about the number of reputation points. That's not what it is. Apply a bit of common sense here. –  Michael Hardy Sep 28 '11 at 15:02