In how many ways the sum of 5 thrown dice is 25?

What I thought about is looking for the number of solutions to $$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=25$$ such that $1\leq x_{i}\leq6$ for every $i$.

Now I know that the number of solutions to this such that $0\leq x_{i}$ for every $i$ is $${5+25-1 \choose 5-1}={29 \choose 4}$$

How can I continue from here?

Thanks


Solution 1:

We want the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 25 \tag{1}$$ subject to the constraints that $1 \leq x_k \leq 6$ for $1 \leq k \leq 5$.

Method 1: If there were no restrictions, a particular solution of equation 1 corresponds to the placement of four addition signs in the $24$ spaces between successive ones in a row of $25$ ones. For instance, $$1 1 1 1 1 1 + 1 1 1 1 + 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1$$ corresponds to the (prohibited) solution $x_1 = 6$, $x_2 = 4$, $x_3 = 8$, and $x_4 = 7$. Thus, the number of solutions of equation 1 in the positive integers is the number of ways we can fill four of the $24$ spaces between successive ones in a row of $25$ ones with addition signs, which is $$\binom{24}{4}$$

More generally, the equation $$x_1 + x_2 + x_3 + \cdots + x_k = n$$ has $$\binom{n - 1}{k - 1}$$
solutions in the positive integers since a particular solution corresponds to the placement of $k - 1$ addition signs in the $n - 1$ spaces between successive ones in a row of $n$ ones.

From these solutions of equation 1, we must exclude those cases in which one or more of the variables exceeds $6$. Since $4 \cdot 7 + 1 = 29 > 25$, at most three of the variables can exceed $6$ simultaneously.

Suppose $x_1 > 6$. Then $y_1 = x_1 - 6$ is a positive integer. Substituting $y_1 + 6$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 6 + x_2 + x_3 + x_4 + x_5 & = 25\\ y_1 + x_2 + x_3 + x_4 + x_5 & = 19 \tag{2} \end{align*} Equation 2 is an equation in the positive integers with

$$\binom{19 - 1}{5 - 1} = \binom{18}{4}$$

solutions. By symmetry, there are equal number of solutions for each variable that could exceed $6$. Hence, there are

$$\binom{5}{1}\binom{18}{4}$$

solutions in which a variable exceeds $6$.

However, if we subtract these from the total, we have subtracted too much since we have subtracted each case in which two variables exceed six twice, once for each way we could designate one of the variables as the one that exceeds six. We only want to subtract them once, so we must add them back.

Suppose $x_1 > 6$ and $x_2 > 6$. Let $y_1 = x_1 - 6$ and $y_2 = x_2 - 6$. Then $y_1$ and $y_2$ are positive integers. Substituting $y_1 + 6$ for $x_1$ and $y_2 + 6$ for $x_2$ in equation 1 yields \begin{align*} y_1 + 6 + y_2 + 6 + x_3 + x_4 + x_5 & = 25\\ y_1 + y_2 + x_3 + x_4 + x_5 & = 13 \tag{3} \end{align*} Equation 3 is an equation in the positive integers with

$$\binom{13 - 1}{5 - 1} = \binom{12}{4}$$

solutions. By symmetry, there are an equal number of cases in which any two of the variables exceed $6$. Hence, there are

$$\binom{5}{2}\binom{12}{4}$$

cases in which two of the variables exceed $6$.

However, if we first subtract those cases in which one of the variables and then add those cases in which two of the variables exceed six, we have not subtracted those cases in which three of the variables exceed six since we subtract each case three times, once for each of the $\binom{3}{1}$ ways of designating one of the variables as exceeding six, and add them three times, once for each of the $\binom{3}{2}$ ways of designating two of the variables as exceeding six.

Suppose $x_1$, $x_2$, and $x_3$ each exceed six. Let $y_1 = x_1 - 6$, $y_2 = x_2 - 6$, and $y_3 = x_3 - 6$. Then $y_1$, $y_2$, and $y_3$ are positive integers. Substituting $y_1 + 6$ for $x_1$, $y_2 + 6$ for $x_2$, and $y_3 + 6$ for $x_3$ in equation 1 yields \begin{align*} y_1 + 6 + y_2 + 6 + y_3 + 6 + y_4 + y_5 & = 25\\ y_1 + y_2 + y_3 + x_4 + x_5 & = 7 \tag{4} \end{align*} Equation 4 is an equation in the positive integers with

$$\binom{7 - 1}{5 - 1} = \binom{6}{4}$$

solutions. By symmetry, there are the same number of solutions in which any three of the variables exceed $6$. Hence, there are

$$\binom{5}{3}\binom{6}{4}$$

cases in which three of the variables exceed $6$.

By the Inclusion-Exclusion Principle, the number of ways the sum of the values on the five dice can equal $25$ is

$$\binom{24}{4} - \binom{5}{1}\binom{18}{4} + \binom{5}{2}\binom{12}{4} - \binom{5}{3}\binom{6}{4}$$

Method 2: Notice that when five dice are rolled, there are the same number of cases in which the values on the dice have sum $6$ (all ones) as have sum $30$ (all sixes), the same number of cases in which the values on the dice have sum $7$ (four ones and a two) as have sum $29$ (four sixes and a five), et cetera. These dual problems have the same number of solutions.

Since the expected value of a single throw is $$\frac{1 + 2 + 3 + 4 + 5 + 6}{6} = 3.5$$ by linearity of expectation, the expected value of five throws is $5 \cdot 3.5 = 17.5$. Since $25 > 17.5$, we can reduce the number of exclusions we need to make by solving the dual problem.

We can solve the dual problem by making the substitutions $y_k = 7 - x_k$ for $1 \leq k \leq 5$. Substituting $7 - y_k$ for $x_k$, $1 \leq k \leq 5$ yields $$y_1 + y_2 + y_3 + y_4 + y_5 = 10$$ Note that each $y_k$ is a positive integer not exceeding $6$. With this substitution, there are no cases in which a variable exceeds $6$ since $7 + 4 \cdot 1 = 11$. Hence, the number of solutions is simply

$$\binom{10 - 1}{5 - 1} = \binom{9}{4}$$

Solution 2:

When we multiply polynomials the formula is

$$ \left( \sum_i a_ix^i \right)\left( \sum_j b_jx^j \right) = \sum_k \left( \sum_{i + j = k} a_ib_j \right) x^k. $$

For a product of $5$ polynomials, we have:

$$ \left( \sum_{i_1} a_{1, i_1}x^{i_1} \right)\left( \sum_{i_2} a_{2, i_2}x^{i_2} \right)\left( \sum_{i_3} a_{3, i_3}x^{i_3} \right)\left( \sum_{i_4} a_{4, i_4}x^{i_4} \right)\left( \sum_{i_5} a_{5, i_5}x^{i_5} \right)$$

$$= \sum_k \left( \sum_{i_1 + i_2 + i_3 + i_4 + i_5 = k} a_{1,i_1}a_{2,i_2}a_{3,i_3}a_{4,i_4}a_{5,i_5} \right) x^k. $$

In particular notice the sum is over all solutions to $i_1 + i_2 + i_3 + i_4 + i_5 = k$. Here we want $k = 25$ and we want $a_{1,i_1}a_{2,i_2}a_{3,i_3}a_{4,i_4}a_{5,i_5} = 1$ except when $i_1, i_2, i_3, i_4$ or $i_5$ is $0$ or $> 6$ in which case we want $0$.

Thinking about this for a minute, we know that we want the coefficient on $x^{25}$ in the product

$$ (x + x^2 + x^3 + x^4 + x^5 + x^6)^5. $$

The polynomial $x + x^2 + x^3 + x^4 + x^5 + x^6$ is telling us that each die can be either $1,2,3,4,5$ or $6$ and each number occurs exactly once.

Let $[x^{n}]f(x)$ denote the coefficient of $x^n$ in $f(x)$. Then we have

\begin{align} [x^{25}](x + x^2 + x^3 + x^4 + x^5 + x^6)^5 &= [x^{25}] \left(\frac{x(1 - x^6)}{1 - x} \right)^5 \\ &= [x^{25}] x^5\left(\frac{1 - x^6}{1 - x} \right)^5 \\ &= [x^{20}] \left(\frac{1 - x^6}{1 - x} \right)^5 \\ &= [x^{20}] (1 - x^6)^5 \frac{1}{(1 - x)^5} \\ &= [x^{20}] \left( \sum_{k = 0}^5 \binom{5}{k} (-1)^kx^{6k} \right) \frac{1}{(1 - x)^5} \\ &= \sum_{k = 0}^5 \binom{5}{k} (-1)^k [x^{20}]x^{6k} \frac{1}{(1 - x)^5} \\ &= \sum_{k = 0}^5 \binom{5}{k} (-1)^k [x^{20 - 6k}] \frac{1}{(1 - x)^5} \\ &= \sum_{k = 0}^3 \binom{5}{k} (-1)^k [x^{20 - 6k}] \frac{1}{(1 - x)^5} \end{align}

We change the upper limit from $5$ down to $3$ because we need $20 - 6k$ to be $\ge 0$ (equivalently, this says we can only have at most three of the dice equal to $6$). Continuing, we get

$$ \sum_{k = 0}^3 \binom{5}{k} (-1)^k [x^{20 - 6k}] \sum_{j} \binom{5 + j - 1}{j}x^j $$

telling us that $j = 20 - 6k$ and finally this gives us

$$ \sum_{k = 0}^3 \binom{5}{k} (-1)^k \binom{5 + (20 - 6k) - 1}{20 - 6k} = \sum_{k = 0}^3 \binom{5}{k} \binom{24 - 6k}{20 - 6k} (-1)^k = 126. $$

Solution 3:

In addition to my other answer using generating functions, I want to offer a more elementary solution. First note that

$$ 5 + 5 + 5 + 5 + 5 = 25 $$

and this is the only way to make $25$ without using a $6$.

Now make one of the dice a $6$ (5 possible ways) to get the equation

$$ a + b + c + d = 19 $$

where $1 \le a, b, c, d \le 19$. Again, the best you can do without a $6$ is

$$4 + 5 + 5 + 5 = 19$$

and there are $4$ of these (one for each position of the $4$.

Now remove a second $6$ to get the equation

$$ a + b + c = 13. $$

Without $6$'s this has two solutions:

$$ 3 + 5 + 5 = 13, $$

which occurs three times, and

$$ 4 + 4 + 5, $$

which also occurs three times.

Remove three $6$'s to get

$$ a + b = 7 $$

which has $4$ solutions not involving a $6$.

Finally remove four $6$'s to get

$a = 1$

with exactly one solution.

Hence in total we have

$$ \binom{5}{0}1 + \binom{5}{1} 4 + \binom{5}{2} 6 + \binom{5}{3} 4 + \binom{5}{4} = 126. $$

The binomial coefficients indicate how many $6$'s we have.

Solution 4:

It is the coefficient of $x^{25}$ in the expression $(x+x^2+x^3+x^4+x^5+x^6)^5$. Which is $\color{red}{126}$.