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

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

• There is some ambiguity, it depends on whether we consider the dice to be distinguishable (probably) or not. Organized counting should do it. Oct 26, 2014 at 18:06
• @AndréNicolas, Do you mean that distinguishable as in Dice1, dice2 and dice3? Organized counting would be the order we add them?
– yiyi
Oct 26, 2014 at 18:30
• Yes, if we consider them different then $(1,6,6)$, $(6,1,6)$ and $(6,6,1))$ are different. By organized counting I mean making sure we don't miss any, maybe by counting first the cases where smallest is $1$, then smallest is $2$, and so on. Oct 26, 2014 at 18:35

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

• hey damn thanks for explaining this so well... just want to know in which book(s) these generating functions are explained in depth or if you have any recommended list of books in which this and such topics are well explained, will love to dig in
– Maha
Oct 28, 2014 at 8:20
• @awellwisher: I recommend H. Wilf's Generatingfunctionology. You may also have a look at this answer. Regards, Dec 2, 2014 at 15:17
• This is a great answer, with only one piece that is unclear to me. In the step you say "From here we can build...", I can't see why the $\sum_{h=0}^{\infty}$ disappears, and more importantly, why $x^3$ and $x^{6j}$ are dropped? Dec 20, 2019 at 7:39

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

• Ah, very good answer indeed! I dont knew this notation. It seems easier to work these probabilities using this notation just that explicit generating functions. Jan 8, 2017 at 9:52
• @Masacroso: glad of your appreciation. Actually, the combination of the explicit formula and of the o.g.f. provides provides a quite wide view of the properties of $N_b$ coefficients. I've been studying this subject for a while, because of its practical applications in Availability and Digital transmission. You might in fact appreciate the application of this to the Bernoulli Runs as in this post Jan 8, 2017 at 12:45
• By chance, I found this answers of yours. Once again, I learn a lot with your answers ! Nov 23, 2017 at 15:06
• @JeanMarie: thanks Jean Marie: same for me with yours ! Nov 23, 2017 at 16:37
• I am fascinated by these " Young tableaux" techniques which bring a fresh air and sometimes a deep insight to many questions. Nov 23, 2017 at 16:55

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.

• hey will like to know step by step solution, poor at maths :'(
– Maha
Oct 26, 2014 at 18:08
• I also do not understand how you came to this answer.
– yiyi
Oct 26, 2014 at 18:31
• sir u r genius, but please help me to learn your answer a bit more, it seems that the things that are obvious to you are not obvious to me. I just didnt get (1) how the final answer is coefficient of $x^{13}$ in the product $(x+x^2 + x^3 + x^4+ x^5 + x^6)^3$, I mean whats the theory behind this? is there any specific underlying concept to which this problem belong? and (2) possibly stupid question to portray my poor algebraic skills: how $(x+x^2 + x^3 + x^4+ x^5 + x^6)^3$ = $x^3(1+ x + x^2 + x^3 + x^4 + x^5)^3$
– Maha
Oct 26, 2014 at 19:39
• @awellwisher I added some explanation. This is all part of a standard counting technique called "generating functions", which is quite powerful. Oct 27, 2014 at 17:52
• @HennoBrandsma damn thanks for explaining this so well... just want to know in which book(s) these generating functions are explained in depth or if you have any recommended list of books in which this and such topics are well explained, will love to dig in
– Maha
Oct 28, 2014 at 8:21

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

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.

• yess answer seems to be 21 as I also enumerated them using C# program here
– Maha
Oct 26, 2014 at 19:07

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