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.

Solution 1:

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.

Solution 2:

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.

Solution 3:

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$.

Solution 4:

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}$

Solution 5:

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.