4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is some ambiguity, it depends on whether we consider the dice to be distinguishable (probably) or not. Organized counting should do it. $\endgroup$ – André Nicolas Oct 26 '14 at 18:06
  • $\begingroup$ @AndréNicolas, Do you mean that distinguishable as in Dice1, dice2 and dice3? Organized counting would be the order we add them? $\endgroup$ – yiyi Oct 26 '14 at 18:30
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 26 '14 at 18:35
11
$\begingroup$

Expanding the answer of Henno Brandsma: a classic generating function (polynomial type) is a way to express combinations (choices) of elements in a parenthesis, where every coefficient represent the frequency of the exponent.

When you throw a standard dice you can take numbers from $1$ to $6$, this is represented in a parenthesis where the polynomial have it exponents representing the values from $1$ to $6$, i.e. the representation of a standard dice is

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

Because we are throwing $3$ dice all possible combinations will be represented as the generating function

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

The polynomial $f(x)$ represent the partial sum of a geometric series, i.e.

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

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

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}$). Hence

$$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$. Any exponent of $x$ will be of the form $S=3+6j+h$, hence we know that $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 expression $[x^k]f(x)$ represent the coefficient that the power $x^k$ have in the function $f(x)$.

We can use this last formula to know the amount of ways to obtain a sum $S$ throwing $3$ dice, in our case for $S=13$. The 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 addend of the sum is 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)$:

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


[*] 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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – anir123 Oct 28 '14 at 8:20
  • $\begingroup$ @awellwisher I just understood by practice and examples of different applications of these classic generating functions here, in mathexchange. They have A LOT of uses for very different problems. Anyway my knowledge is so limited on this matter. $\endgroup$ – Masacroso Oct 28 '14 at 8:22
  • 2
    $\begingroup$ @awellwisher: I recommend H. Wilf's Generatingfunctionology. You may also have a look at this answer. Regards, $\endgroup$ – Markus Scheuer Dec 2 '14 at 15:17
11
$\begingroup$

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] http://www.mathpages.com/home/kmath337.htm
[4] http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf
[5] https://oeis.org/A008287

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Masacroso Jan 8 '17 at 9:52
  • $\begingroup$ @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 $\endgroup$ – G Cab Jan 8 '17 at 12:45
  • $\begingroup$ By chance, I found this answers of yours. Once again, I learn a lot with your answers ! $\endgroup$ – Jean Marie Nov 23 '17 at 15:06
  • $\begingroup$ @JeanMarie: thanks Jean Marie: same for me with yours ! $\endgroup$ – G Cab Nov 23 '17 at 16:37
  • $\begingroup$ I am fascinated by these " Young tableaux" techniques which bring a fresh air and sometimes a deep insight to many questions. $\endgroup$ – Jean Marie Nov 23 '17 at 16:55
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ hey will like to know step by step solution, poor at maths :'( $\endgroup$ – anir123 Oct 26 '14 at 18:08
  • $\begingroup$ I also do not understand how you came to this answer. $\endgroup$ – yiyi Oct 26 '14 at 18:31
  • $\begingroup$ 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$ $\endgroup$ – anir123 Oct 26 '14 at 19:39
  • $\begingroup$ @awellwisher I added some explanation. This is all part of a standard counting technique called "generating functions", which is quite powerful. $\endgroup$ – Henno Brandsma Oct 27 '14 at 17:52
  • $\begingroup$ @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 $\endgroup$ – anir123 Oct 28 '14 at 8:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yess answer seems to be 21 as I also enumerated them using C# program here $\endgroup$ – anir123 Oct 26 '14 at 19:07
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.