Expansion of Generating Functions

426 Views Asked by At

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

3

There are 3 best solutions below

0
On

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.

0
On

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.

0
On

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