2
$\begingroup$

If you roll $10$ dice, how many ways can you get a total sum of top faces of $25$?

I understand how to write the generating function of $(x+x^2+ \dots +x^6)^{10}$ and the fact that you need to find the coefficient of $x^{25}$, but how do you do this? The conventional binomial theorem only works for binomial expansion....

$\endgroup$
  • $\begingroup$ You should not have a 1 in your generating function in this scenario. $\endgroup$ – JMoravitz Jun 6 '15 at 21:49
  • $\begingroup$ Oh yeah you're right because there can't be a 0 for the top face. $\endgroup$ – DeepakM Jun 7 '15 at 1:02
2
$\begingroup$

I should mention, this answer assumes the dice are distinct. (e.g. you have a red die, a blue die, a green die, etc... or a "first die" a "second die" a "third die", etc...)

We know that each result on the die is minimum 1, so let us ask a similar question instead to simplify the arithmetic involved: What is the coefficient of $x^{15}$ in the expansion of $(1+x+x^2+\dots+x^5)^{10}$.

Find how many ways you can add to 15 using 1's, 2's, 3's, etc in decreasing order using at most 10 positive integers less than or equal to 5.

$$\begin{array}{l}5+5+5\\ 5+5+4+1\\ 5+5+3+2\\ 5+5+3+1+1\\ 5+5+2+2+1\\ 5+5+2+1+1+1\\ 5+5+1+1+1+1+1\\ 5+4+4+2\\ \color{red}{5+4+4+1+1}\\ 5+4+3+3\\ 5+4+3+2+1\\ 5+4+3+1+1+1\\ 5+4+2+1+1+1+1\\ 5+4+1+1+1+1+1+1\\ \vdots\\ 2+2+2+2+2+1+1+1+1+1\end{array}$$

For each of these, you can calculate their specific contribution. The line colored red for example occurs when you use one occurrence of $x^5$, two occurrences of $x^4$, two occurrences of $x^1$, and the remaining five occurrences as $x^0$. If you were to reimagine this as finding the coefficient of $A^1B^2C^2D^5$ in the expansion of $(A+B+C+D+E+F)^{10}$, it will be $\binom{10}{1,2,2,5}=\frac{10!}{1!2!2!5!}$.

I.e., the red line corresponds to rolling one 6, two 5s, two 2s, and five 1s.

Find the contribution of each case separately and add them together.


Of course, this is a very tedious process to do by hand, and so it is much easier to simply ask a calculator to expand $(1+x+x^2+x^3+x^4+x^5)^{10}$ and find the coefficient that way.

Wolfram shows that it is $831204$


If you are curious in the number of ways you can do so where the dice are indistinct, just count how many ways are in the list above.

$\endgroup$
1
$\begingroup$

Write $x+x^2+\cdots+x^6$ as $(1-x^7)(1-x)^{-1}$. Then $$\begin{align} [x^{25}]&(x+x^2+\cdots+x^6)^{10}\\ &=[x^{25}](x-x^7)^{10}(1-x)^{-10}\\ &=[x^{15}](1-x^6)^{10}(1-x)^{-10}\\ &=[x^{15}]\sum_{r\ge0}\binom{10}r(-x^6)^r \sum_{s\ge0}\binom{-10}s(-x)^s\\ &=\sum_{r\ge0}(-1)^r\binom{10}r\binom{10+s-1}{10-1}\quad\textrm{with $s=15-6r$}\\ &=\sum_{r=0}^2(-1)^r\binom{10}r\binom{24-6r}{9}\quad\textrm{noting $15-6r\ge0$}\\ &=\binom{10}0\binom{24}9 -\binom{10}1\binom{18}9 +\binom{10}2\binom{12}9\\ &=831204 \end{align}$$

$\endgroup$
1
$\begingroup$

The generalization of the binomial expansion is the multinomial expansion: $$ (x_1+x_2+\ldots+x_k)^{n}=\sum_{j_1+j_2+\ldots+j_k=n}\frac{n!}{j_1!j_2!\ldots j_k!}x_1^{j_1}x_2^{j_2}\ldots x_k^{j_k}. $$ In your case (omitting the erroneous $1$ in your g.f.), $$ (x+x^2+\ldots + x^6)^{10}=\sum_{j_1+j_2+\ldots+j_6=10}\frac{10!}{j_1!j_2!\ldots j_6!}x^{j_1 + 2j_2 + 3j_3 + 4j_4 + 5j_5 + 6j_6}. $$


Or, think of it as splitting $25$ spots among $10$ dice, with the constraint that there must be from $1$ to $6$ spots per die. Using inclusion-exclusion, this is the number of ways to split $25$ spots among $10$ dice with no constraint (except at least $1$ spot per die), minus the number of ways to do so with at least $7$ on some die, plus the number of ways to do so with at least $7$ on two dice, and so on. When you've decided which dice must have at least $7$, you can assign $6$ dots to each of those immediately and then divide the rest with the same constraint (at least $1$ spot per die). There can't be at least $7$ on more than two dice, so this terminates quickly: $$ N={{24}\choose{9}}-{{10}\choose{1}}{{18}\choose{9}}+{{10}\choose{2}}{{12}\choose{9}}=831204. $$ Note that the negative binomial expansion used in another answer formalizes this approach.

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