generating function: how many possibilities are there to throw 10 different dice so that their sum is 25

Question

My discrete math textbook has the following solution to the problem using generating functions (the solution has to use generating functions):

$$f(x)=(x+x^2+x^3+x^4+x^5+x^6)^{10}$$

Once we start developing the formal power series we get the following:

$$x^{10}(1-x^6)^{10}\frac{1}{(1-x)^{10}}$$ Because of $x^{10}$ we now need to find the coefficient of only $x^{15}$: $$\binom{10}{0}\binom{10-1+15}{15}-\binom{10}{1}\binom{10-1+9}{9}+\binom{10}{2}\binom{10-1+3}{3}$$ I completely understand the first two expressions but why are we using the third one: $$\binom{10}{2}\binom{10-1+3}{3}$$ Where does the $3$ come from and why this isn't enough: $$\binom{10}{0}\binom{10-1+15}{15}-\binom{10}{1}\binom{10-1+9}{9}$$ ?

Answer 1

The coefficient of $x^{25}$ in $(x+x^2+\ldots+x^6)^{10}$ equals the coefficient of $x^{15}$ in $$ (1+x+\ldots+x^5)^{10} = (1-x^6)^{10}\cdot\frac{1}{(1-x)^{10}} $$ so the answer is given by $$ [x^{15}] \left(\sum_{k=0}^{10}\binom{10}{k}(-1)^k x^{6k}\right)\cdot\left(\sum_{j\geq 0}\binom{9+j}{j}x^j\right) $$ and it is enough to consider just the terms associated with $k=0,1,2$, since $x^{6k}$ has an exponent greater than $15$ for any $k>2$. By computing the Cauchy product between the above series it follows that the answer is given by: $$ \underbrace{\binom{10}{0}\binom{24}{15}}_{k=0,\;j=15}-\underbrace{\binom{10}{1}\binom{18}{9}}_{k=1,\;j=9}+\underbrace{\binom{10}{2}\binom{12}{3}}_{k=2,\;j=3}.$$

Answer 2

As opposed to generating functions, I personally learned to solve this question via inclusion exclusion.

We were looking for the number of integer solutions to the system: $\begin{cases} x_1+x_2+\dots+x_{10}=25\\ 1\leq x_i\leq 6&\text{for all}~i\end{cases}$

Through a change of variable, we have instead the system $\begin{cases}y_1+y_2+\dots+y_{10}=15\\ 0\leq y_i\leq 5\end{cases}$

Approaching via inclusion-exclusion on the events that the respective upper bound conditions are violated. Let $S$ be where we ignore any upper bound conditions. Let $A_i$ be the set where the $i$'th upper bound condition is violated. The total with no upperbound conditions violated is:

$$|S|-\sum\limits_{i=1}^{10}|A_i|+\sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}|A_i\cap A_j| - \sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}\sum\limits_{k=j+1}^{10}|A_i\cap A_j\cap A_k|+\dots$$

if we have no upper bound conditions violated, there are $\binom{10+15-1}{15}$ solutions. If one upper bound condition is violated, pick which one. Each of which will have a total of $\binom{10+9-1}{9}$ solutions for a total of $\binom{10}{1}\binom{18}{9}$ needing to be removed from the count. If two upperbound conditions are violated, pick which two they are. Each of which will have a total of $\binom{10+3-1}{3}$ solutions for a total of $\binom{10}{2}\binom{12}{3}$ needing to be added back. Three upperbound conditions being simultaneously violated is impossible.

This gives, again the solution of:

$$\binom{10}{0}\binom{24}{15}-\binom{10}{1}\binom{18}{9}+\binom{10}{2}\binom{12}{3}$$

The explanation for the final term being with this understanding, that you had subtracted the same "bad outcomes" from your total too many times otherwise. Why we use a $3$ would be from how we solve the question of finding how many violate the $i$'th and $j$'th upperbound conditions. Suppose $i=1$ and $j=2$, we have then the system:

$\begin{cases} y_1+y_2+\dots+y_{10}=15\\ 6\leq y_1\\ 6\leq y_2\\ 0\leq y_3\\ \vdots \\ 0\leq y_{10}\end{cases}$

After a change of variable, we have the system

$\begin{cases} z_1+z_2+\dots+z_{10}=3\\ 0\leq z_i\end{cases}$ which is of a known form.