0
$\begingroup$

I've been assigned this problem:

Find the number of ways to obtain a total of $15$ points by throwing $4$ different dice?

The problem can be stated as:

$$x_1+x_2+x_3+x_4=15\text{ with } 1\leq x_n \leq 6$$

And also as coefficient of $x^{15}$ in the generating function:

$$\left[ \sum_{r=1}^6x^r \right]^4$$

But I don't know how to compute the coefficient of $x^{15}$, until now, most problems involved the product of small generating functions and it was easy to calculate by summing the powers up to a certain number. But in this case, it's not. What could be done to calculate this by hand? I have the slight impression that I could write:

$$\left[ \sum_{r=1}^6x^r \right]^4=\left[\frac{1-x^{n+1}}{1-x}\right]^4$$

But I don't know what to do from here (considering its possible/meaninful to do this).

$\endgroup$
1
$\begingroup$

We have

$$\sum_{r=1}^6 x^r=\frac{x-x^7}{1-x}$$

Thus using binomial theorem we have

$$\begin{aligned}&\left[\sum_{r=1}^6 x^r\right]^4=x^4(1-x^6)^4(1-x)^{-4}\\ =&x^4\left(\sum_{r=0}^4(-1)^r\binom{4}{r}x^{6r}\right)\left(\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\right)\\ =&\left(\sum_{r=0}^4(-1)^r\binom{4}{r}x^{6r+4}\right)\left(\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\right)\\ =&\sum_{r=0}^4\left[(-1)^r\binom{4}{r}x^{6r+4}\left(\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\right)\right]\\ =&\sum_{r=0}^4\left(\sum_{k=0}^\infty\left((-1)^r\binom{4}{r}x^{6r+4}\right)\left((-1)^k\binom{-4}{k}x^k\right)\right)\\ =&\sum_{r=0}^4\sum_{k=0}^\infty\left((-1)^{r+k}\binom{4}{r}\binom{-4}{k}x^{k+6r+4}\right)(*) \end{aligned}$$

Here we recall the definition of binomial coefficient: for any $\alpha\in\mathbb{R}$ and $k\in\mathbb{N}$, the binomial coefficient "$\alpha$ choose $k$" is

$$\binom{\alpha}{k}=\frac{\alpha(\alpha-1)\dots(\alpha-(k-1))}{k!}$$

and the binomial theorem says

$$(a+b)^{\alpha}=\sum_{k=0}^\infty\binom{\alpha}{k}a^{\alpha-k}b^k$$

Now we look at the $x^{15}$ term in $(*)$, this is equivalent to solve $k+6r+4=15$ where $r=0,1,2,3,4$ and $k=0,1,2,\dots$. The only possibilities are $r=0,k=11$ and $r=1, k=5$, and the correponding coefficients are $(-1)^{11}\binom{4}{0}\binom{-4}{11}$ and $(-1)^{6}\binom{4}{1}\binom{-4}{5}$, by adding them we get the coefficient for the $x^{15}$ term :

$$\begin{aligned}&(-1)^{11}\binom{4}{0}\binom{-4}{11}+(-1)^6\binom{4}{1}\binom{-4}{5}\\ =&(-1)^{11}\frac{(-4)(-5)\dots(-4-(11-1))}{11!}+4\cdot(-1)^6\frac{(-4)(-5)\dots(-4-(5-1))}{5!}\\ =&\frac{4\cdot 5\cdot\dots\cdot 14}{11!}-4\frac{4\cdot\dots\cdot 8}{5!}\\ =&\frac{14!}{3!11!}-4\frac{8!}{3!5!}\\ =&140 \end{aligned}$$

$\endgroup$
  • $\begingroup$ Great! Thank you very much. $\endgroup$ – Billy Rubina Feb 8 '15 at 4:11
  • $\begingroup$ Excuse me, isn't it: $\displaystyle \sum_{r=1}^6 x^r=\frac{1-x^7}{1-x}$ ? $\endgroup$ – Billy Rubina Feb 8 '15 at 4:38
  • $\begingroup$ If sum from $r=0$, then it is $\sum_{r=0}^6x^r=\frac{1-x^7}{1-x}$ $\endgroup$ – Frank Lu Feb 8 '15 at 4:41
  • $\begingroup$ Why if the sum from $r=0$ make it become $\frac{x-x^7}{1-x}$? $\endgroup$ – Billy Rubina Feb 8 '15 at 4:44
  • 1
    $\begingroup$ perhaps this is helpful:en.wikipedia.org/wiki/Geometric_series $\endgroup$ – Frank Lu Feb 8 '15 at 4:46
0
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ Each argument $\ds{\delta_{x_{1} + \cdots + x_{4}\,,15}\ }$ in the multiple sum $\ds{\sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6} \delta_{x_{1} + \cdots + x_{4}\,,15}\ }$ is equal to $\underline{one}$ whenever $\ds{x_{1} + \cdots + x_{4}=15}$ and it becomes $\underline{zero}$ otherwise such that the sum counts the number of combinations of $\ds{x_{j}, j=1,2,3,4}$ which add to $\underline{15}$.

$\ds{\delta_{m,n}}$ is the Kronecker Delta: It's equal to $\underline{one}$ when $\ds{m=n}$ and it's equal to $\underline{zero}$ when $\ds{m \not= n}$. In order to perform the multiple sum it's convenient to use a Kronecker Delta integral representation: $$ \delta_{m,n}=\oint_{\verts{z}=R}\ \frac{1}{z^{-m + n + 1}}\,\frac{\dd z}{2\pi\ic}\,;\qquad R > 0\,, \quad m,n\in{\mathbb Z} $$


We'll choose a value of $\ds{R}$ that satisfies $\ds{0 < R < 1}$: It lets us to enclose just one pole in a complex integration $\ds{\pars{~\mbox{see below}~}}$:

\begin{align}&\color{#66f}{% \sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6}\delta_{x_{1} + \cdots + x_{4}\,,15}}\ =\sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6}\oint_{\verts{z}=R}\ \frac{1}{z^{-x_{1} - \cdots - x_{4} + 16}}\,\frac{\dd z}{2\pi\ic} \\[5mm]&=\oint_{\verts{z}=R}\frac{1}{z^{16}}\sum_{x_{1}=1}^{6}z^{x_{1}} \sum_{x_{2}=1}^{6}z^{x_{2}}\sum_{x_{3}=}^{6}z^{x_{3}}\sum_{x_{4}=1}^{6}z^{x_{4}} \,\frac{\dd z}{2\pi\ic} \end{align} As all the sums over $\ds{x_{j},j=1,2,3,4}$, are identical, the last expression leads to: \begin{align} &\color{#66f}{% \sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6}\delta_{x_{1} + \cdots + x_{4}\,,15}}\ =\oint_{\verts{z}=R} \frac{1}{z^{16}}\pars{\sum_{x=1}^{6}z^{x}}^{4}\,\frac{\dd z}{2\pi\ic} \\[5mm]&=\oint_{\verts{z}=R} \frac{1}{z^{16}}\pars{z\,\frac{1 - z^{6}}{1 - z}}^{4}\,\frac{\dd z}{2\pi\ic} =\oint_{\verts{z}=R} \frac{\pars{1 - z^{6}}^{4}}{z^{12}\,\pars{1 - z}^{4}}\,\frac{\dd z}{2\pi\ic} \end{align}


In order to perform the complex integration we'll use the expansion $\ds{\frac{1}{\pars{1 - z}^{4}}=\sum_{j=0}^{\infty}\ \overbrace{\pars{-4 \atop \phantom{-}j}} ^{\dsc{\pars{j + 3 \atop 3}\pars{-1}^{j}}}\pars{-z^{j}} =\sum_{j=0}^{\infty}\pars{j + 3 \atop 3}z^{j}}$ and the $\ds{\pars{1 - z^{6}}^{4}}$ binomial expansion:
\begin{align} &\color{#66f}{% \sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6}\delta_{x_{1} + \cdots + x_{4}\,,15}}\ =\sum_{k=0}^{4}\binom{4}{k}\pars{-1}^{k} \sum_{j=0}^{\infty}\binom{j + 3}{j}\ \overbrace{\oint_{\verts{z}=R} \frac{1}{z^{12 - 6k - j}}\,\frac{\dd z}{2\pi\ic}} ^{\dsc{\delta_{6k + j,11}}} \\[5mm]&=\left.\sum_{k=0}^{4}\sum_{j=0}^{\infty}\binom{4}{k}\binom{j + 3}{3}\pars{-1}^{k} \right\vert_{\, 6k + j=11} \end{align} The values of $\ds{k,j}$ which satisfy $\ds{6k + j = 11}$ are $\ds{\pars{k=0,j=11}}$ and $\ds{\pars{k=1,j=5}}$ such that: \begin{align} &\color{#66f}{\large% \sum_{x_{1}=1}^{6}\ldots\sum_{x_{4}=1}^{6}\delta_{x_{1} + \cdots + x_{4}\,,15}}\ =\binom{4}{0}\binom{14}{3}\pars{-1}^{0} +\binom{4}{1}\binom{8}{3}\pars{-1}^{1} \\[5mm]&=1\times 364 - 4\times 56=\color{#66f}{\large 140} \end{align}

$\endgroup$
  • $\begingroup$ Thanks for your answer. Could you clarify a little bit on your steps? Your answer seems really interesting, but it's not really clear what you are doing there: It seems that you're using techniques of analysis (some kind of treatment of series I never seen before). [Please, do not erase your answer because of my stupidity, leave it there and write a little bit on every step. Some day this answer might enhance my knowledge a lot]. $\endgroup$ – Billy Rubina Feb 10 '15 at 5:09
  • 1
    $\begingroup$ @Vÿska Thanks. I'll do it: I'll include several details. Be patient. $\endgroup$ – Felix Marin Feb 10 '15 at 19:11
  • $\begingroup$ Who downvoted this?! $\endgroup$ – Billy Rubina Feb 13 '15 at 6:48
  • 1
    $\begingroup$ @Vÿska I add some details to the answer. Don't worry for down-votes. It's part of the business. I have "my" 'bullying hunter' which always check my answers, my comments and even my $\LaTeX$ edition. I don't care. Instead of learning something new he/she prefers to show his/her jealous behavior. $\endgroup$ – Felix Marin Feb 13 '15 at 20:07

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.