If I roll three dice at the same time, how many ways the sides can sum up to $13$? [duplicate]

Question

If I rolled $3$ dice how many combinations are there that result in sum of dots appeared on those dice be $13$?

Answer 1

Expanding the answer of Henno Brandsma: a generating function is a way to pack a sequence as the coefficients of the power expansion of a function, by example we can pack the Fibonacci sequence as the coefficients on the power expansion of the function $h(x):=\frac1{1-x-x^2}$.

The important point here is that the algebra of generating functions (product, sum, etc.) is a handy way to compose the coefficients packed in them to get a new generating function with coefficients that are of interest to us.

By example the polynomial

$$ p(x):=a_0x^0+a_1x^1+a_2x^2+\ldots+a_n x^n $$

is the generating function that contains the sequence $a_0,a_1,\ldots,a_n$.

In our case each side of a standard fair dice appears just once in the dice, that is, there is only one side with a given number, from one to six. Therefore the generating function

$$ f(x):= x^1+x^2+x^3+x^4+x^5+x^6 $$

pack the sequence of number of sides of a fair die (note that the power of each monomial represent one of the sides of a dice).

Now: multiplication of generating functions have the effect that the new sequence, after multiplication, is a sum of products of the old ones, where the indices of every product in each sum add up to the exponent of the monomial that will accompany.

Its easy to check that, as we are throwing three dice, then the generating function

$$g(x):=f(x)^3=(x^1+x^2+x^3+x^4+x^5+x^6)^3$$

pack as coefficients the total amounts of different ways to add up to the exponent of each monomial.

Now: the polynomial $f$ can be seen as the partial sum of a geometric series, i.e.

$$ \begin{align*} f(x)&=x^1+x^2+x^3+x^4+x^5+x^6\\ &=x(x^0+x^1+x^2+x^3+x^4+x^5)\\ &=x\sum_{k=0}^{5}x^k\\ &=x\frac{1-x^6}{1-x} \end{align*} $$

Then $$g(x)=x^3\left(\frac{1-x^6}{1-x}\right)^3=x^3\color{red}{(1-x^6)^3}\color{green}{(1-x)^{-3}}$$

The colored expressions (red and green) can be expressed as binomial series[*]. Then

$$\require{cancel} g(x)=x^3\color{red}{\sum_{j=0}^{3}(-1)^j\binom{3}{j}x^{6j}}\color{green}{\sum_{h=0}^{\infty}(-1)^h\binom{-3}{h}x^h}$$

Now: as we know that $\binom{-3}{h}=(-1)^h\binom{3+h-1}{h}=(-1)^h\binom{h+2}{2}$ (to understand this equality you can see here, and remember that $\binom{n}{k}=\binom{n}{n-k}$), then we find that

$$g(x)=x^3\color{red}{\sum_{j=0}^{3}(-1)^j\binom{3}{j}x^{6j}}\color{green}{\sum_{h=0}^{\infty}\cancel{(-1)^h}\cancel{(-1)^h}\binom{h+2}{2}x^h}$$

From here we can build a formula to know the coefficient for any exponent of $x$. First note that any exponent of $x$ will be of the form $S=3+6j+h$, so $h=S-3-6j$, and the coefficient for any sum $S$ will be

$$[x^S]g(x)=1\cdot\sum_{j=0}^{3}\color{red}{(-1)^j\binom{3}{j}}\color{green}{\binom{S-3-6j+2}{2}}\\ =\sum_{j=0}^{3}\color{red}{(-1)^j\binom{3}{j}}\color{green}{\binom{S-1-6j}{2}}$$

where the notation $[x^k]f(x)$ represent the coefficient that the power $x^k$ have in the function $f$.

We can use this last formula to know the amount of ways to obtain a sum $S$ throwing three dice, in our case for $S=13$. Indeed the previous formula can be written in a more precise way: observe that if $S-1-6j<2$ (green binomial) or $j>3$ (red binomial) then the addend will be zero, because if $n<k$ for $n,k\in\Bbb N$ then $\binom{n}{k}=0$. Hence the addends of the sum are not zero when $S-1-6j\ge 2$ and $3\ge j$. And the values of $j$ where the addends are not zero are determined by

$$S-1-6j\geq 2 \implies j\leq\frac{S-3}{6}\le\frac{18-3}6<3\implies j\le 3,\quad S\in\{3,4,\ldots,18\}$$

Then we can re-write $[x^S]g(x)$ as

$$\bbox[5px,border:2px solid gold]{[x^S]g(x)=\sum_{j=0}^{\lfloor\frac{S-3}{6}\rfloor}(-1)^j\binom{3}{j}\binom{S-1-6j}{2}}$$

I hope you understand all information. Anyway surely you must read some more info to understand completely this answer. Just to clarify: the notation $\lfloor x\rfloor$ is the representation of the floor function.

To complete the question, we will evaluate $[x^{13}]g(x)$:

$$ \begin{align*}[x^{13}]g(x)&=\sum_{j=0}^{1}(-1)^j\binom{3}{j}\binom{12-6j}{2}\\ &=\binom{3}{0}\cdot\binom{12}{2}-\binom{3}{1}\binom{6}{2}\\ &=1\cdot \frac{\cancelto{6}{12}\cdot 11}{\cancel{2}}-3\cdot \frac{\cancelto{3}{6}\cdot 5}{\cancel{2}}\\ &=6\cdot 11 - 9\cdot 5\\ &=21 \end{align*}$$

---

[*] Observe that for $n\in\Bbb N$

$$(x+y)^n=\sum_{k=0}^\infty\binom{n}{k}x^ky^{n-k}=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}$$

then although the second sum is finite it represent a binomial series with infinite addends that are zero.

Answer 2

the formula introduced by Masacroso applies to a bulk of different schemes in combinatorics and diophantine geometry, all stemming out from finding $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$ (note that here, for generality, the allowed range for the variables is taken as $0\, \ldots \,r$;
the conversion to $1\, \ldots \,6$ for dice problems is quite straight, leading to the formulas already provided above).

It is preferable to express ${N_{\,b} }$ as follows

$$ N_{\,b} (s,r,m)\quad \left| {\;0 \le {\rm integers}\;s,r,m} \right.\quad = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,{s \over r}\, \le \,m} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ m \cr k \cr} \right)\left( \matrix{ s + m - 1 - k\left( {r + 1} \right) \cr s - k\left( {r + 1} \right) \cr} \right)} $$ where the binomial coefficient is defined as

$$\left( \begin{gathered} x \\ q \\ \end{gathered} \right) = \left\{ {\begin{array}{*{20}c} {\frac{{x^{\,\underline {\,q\,} } }} {{q!}}} & {0 \leqslant \text{integer }q} \\ 0 & {\text{otherwise}} \\ \end{array} } \right.$$

re. [1], [2].

When defined in this way, in fact, the limits of summation are implicit in the summand (that is why they are indicated in brackets) and that greatly simplifies further manipulations.

The o.g.f. , as explained in the precedent answer, is $$ F_{\,b} (x,r,m) = \sum\limits_{0\, \le \,s\,\left( { \le \,m\,r} \right)} {N_{\,b} (s,r,m)\;x^{\,s} } = \left( {1 + x + \, \cdots \, + x^{\,r} } \right)^m = \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right)^m $$

Thus $Nb$ can also be expressed in terms of multinomials ..., and that is why it is also called "r-nomial coefficient" (actually, as defined above, an "r+1-nomial"): eg. in OEIS A008287 [5].

$Nb$ satisfies many recurrences, one of which is :

$$\left\{ \begin{gathered} N_{\,b} (s,r,0) = \left[ {0 = s} \right] \hfill \\ N_{\,b} (s,r,m + 1) = \sum\limits_{0\, \leqslant \,j\, \leqslant \,r} {N_{\,b} (s - j,r,m)} \hfill \\ \end{gathered} \right.$$

where: $$\left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right.\text{ }\;\;\text{is the Iverson bracket}$$

and which just corresponds to:

$$F_{\,b} (x,r,m) = \left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)^m = \left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)\left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)^{m - 1} $$

Each way in which $F_{\,b}$ can be rewritten turns into a relation for $N_{\,b}$, for instance
$$ F_{\,b} (x,r,m) = \left( {{{1 - x^{r + 1} } \over {1 - x}}} \right)^{\,m} = \left( {{{1 - x^r } \over {1 - x}} + x^r } \right)^{\,m} = \left( {1 + x\left( {{{1 - x^r } \over {1 - x}}} \right)} \right)^{\,m} $$

And to complete the picture you also have the double o.g.f. $$ G_{\,b} (x,r,z) = \sum\limits_{0\, \le \,s,\,m} {N_{\,b} (s,r,m)\;x^{\,s} \;z^{\,m} } = {1 \over {1 - z{{1 - x^{\,r + 1} } \over {1 - x}}}} $$

The applications include:
a) number of ways to roll $m$ dice, with $r+1$ facets numbered from 0 to r, and getting a total of $s$;
b) number of ways to dispose $s$ indistinguishable balls into $m$ distinguishable bins of capacity $r$ as it is called in many publications,
but, beware that this might be misleading , as is not the model of "throwing balls into bins", rather the reverse of "throwing bins into balls" , in the sense of throwing separators into a row of balls, i.e. the "bars_and_stars" model, but provided that the $m-1$ bars are inserted incrementally, and then with the restriction that they shall not encompass more than $r$ balls ;
c) number of different histograms, with $m$ bars, each bar of length $0\, \ldots \,r$, total length $s$;
d) number of points with integer coordinates, lying on the diagonal plane $x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s$, within a $m$-dimensional cube of side $0\, \ldots \,r$;
e) number of 2-D lattice paths, from $(0,0)$ to $(m,s)$, with steps in $\left( {1,0\, \ldots \,r} \right)$ ;
f) finally note that $N_{\,b}$ recurrence above entails a "moving-window summation" of fixed width 0..r, so that it can be exploited in topics involving that.

The various underlying models provide different perspectives useful to grasp the properties of this function.
It is clear for instance that $N_{\,b} (s,r,m) = N_{\,b} (m\,r - s,r,m)$ because distributing $s$ balls is the same as distributing $m r-s$ voids, or by looking at the complement of the histogram, or by viewing at the $m$-cube from the opposite diagonal corner.

@PardonMe..
A clear, precise and fundamental basis to Generating Functions (and to much more) is given in [1].
[3] provides a general exposition of how this function may be derived (it also deals with the case of bins with different capacities..).
In [4] then, although it deals with partitions, you get a clear picture of how to derive from the o.g.f. the combinatorial properties that it encapsulates, as Masacroso did in his exposition above.

---

[1] "Concrete Mathematics: a foundation for computer science" R. L. Graham - D.E. Knuth - O. Patashnik - Addison-Wesley 2nd Ed. 1994
[2] http://en.wikipedia.org/wiki/Binomial_coefficient
[3] https://www.mathpages.com/home/kmath337/kmath337.htm
[4] http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf
[5] https://oeis.org/A008287
[6] http://arxiv.org/abs/1202.0228v7

Answer 3

It's the coefficient of $x^{13}$ in the product $(x+x^2 + x^3 + x^4+ x^5 + x^6)^3$. To see this, note that to compute that coefficient we have to identify all ways we can form $x^{13}$ by picking one term from each of the three terms $(x + x^2 + x^3 + x^4 + x^5 + x^6)$ we have; we could have $x$ from the first, $x^6$ from the second and the third and this would correspond to throwing $(1,6,6)$ with the three different dice (which we imagine to have different colours to distinguish them). This choice gives us one way to get $x^{13}$ in the final gathering of terms, and all other choices (so pairs $(a,b,c)$ with $a + b + c = 13, 1 \le a,b,c \le 6$) give us one extra power of $x^{13}$. So the final coefficient just counts all those triples.

E.g. try this with two dice: $$(x+x^2 + x^3 + x^4+ x^5 + x^6)^2 = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 5x^8 + 4x^9 + \\ 3x^{10} + 2x^{11} + x^{12}$$ and we see that the coefficient of $x^n$ is just the number of ways we can throw $n$ with two dice.

Write this as $(x(1+x+x^2+x^3+x^4+x^4))^3 = x^3(1+ x + x^2 + x^3 + x^4 + x^5)^3$, so we are looking for the coefficient of $x^{10}$ in $(1+ x + x^2 + x^3 + x^4 + x^5)^3$.

The fancy way to do this is to write $(1+x+x^2+\ldots+x^5) = \frac{1-x^6}{1-x}$ (standard geometric series) and so $(1+ x + x^2 + x^3 + x^4 + x^5)^3 = (1-x^6)^3 (1-x)^{-3}$.

The first term on the right can be evaluated using the binomial formula as $1 - 3x^6 + 3x^{12} - x^{18}$.

The second term on the right can be evaluated by the generalised binomial formula as $\sum_{k=0}^{\infty} {k+2 \choose k} x^k$.

So to get $x^{10}$ from the product of these, we get the $1$ from the first times the ${12 \choose 10}x^{10}$ from the second and the $-3x^6$ from the first times ${6 \choose 4}x^4$ of the second. Other terms have too high powers of $x$.

So the answer is ${12 \choose 10} - 3{6 \choose 4} = 21$.

You can use Wolfram alpha to expand the original polynomial $(1+x+\ldots+x^5)^3$ and we get $$x^{15}+3 x^{14}+6 x^{13}+10 x^{12}+15 x^{11}+21 x^{10}+\\25 x^9+27 x^8+27 x^7+25 x^6+21 x^5+15 x^4+10 x^3+6 x^2+3 x+1$$

The alternative is simple enumeration. But I like the complicated ways, as they generalise to more dice and higher sums. E.g. in the final expansion we see that there are $25$ ways to throw $9+3 = 12$ with three dice, etc. We get all the probabilities for all the sums at the same time.

Answer 4

A practical solution at High School level:

If I throw 2 dice, I have 36 outcomes.

Throw 7 occurs 6 times, and the other 30 are equally divided in 15 times more than 7 and 15 times less than 7.

The 6 and first set of 15 throws can uniquely be completed to 13. The others can't.

$$6+15 = 21$$

Answer 5

Let (x, y, z) be the numbers showing on the 3 dice.
We want x + y + z = 13.
Assuming the dice are distinguishable, the possibilities are:
(1, 6, 6) (2, 5, 6), (2, 6, 5)
(3, 4, 6), (3, 5, 5), (3, 6, 4)
(4, 3, 6), (4, 4, 5), (4, 5, 4), (4, 6, 3) (5, 2, 6), (5, 3, 5), (5, 4, 4), (5, 5, 3), (5, 6, 2)
(6, 1, 6), (6, 2, 5), (6, 3, 4), (6, 4, 3), (6, 5, 2), (6, 6, 1)

So, there are 21 different combinations.

Answer 6

At the lower division math level we can do the following easily given the low number of combinations:

1)list the number of potential combinations 116

265

355

364

454

2) Now we find out the numbers of way that we can arrange the listed numbers in which it is:

3 6 3 6 3 respectively

thus when we add the numbers we get 21