11
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ I think the best way is to add the number of solutions for each of the cases - how many $x_i=6$ $\endgroup$ – Shuri2060 Jul 22 '17 at 18:43
  • $\begingroup$ 1 way to get 25 with 5 5;5 ways to get 25 with 1 + $4\times 6$;15 ways to get 7 with two dice and $3\times 6$; 35 ways to get 13 with 3 dice and $2\times 6$ and 70 ways to get 19 with 4 dice and the 5th. 6. $1+5+15+35+70=126$ $\endgroup$ – Raffaele Jul 23 '17 at 19:28
14
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ The summation you get from the generating function has a factor of $\binom{5}{k}(-1)^k$ which heavily suggests inclusion-exclusion so your first method nicely complements the generating function answer. Your second method takes the prize for slickest solution. $\endgroup$ – Trevor Gunn Jul 22 '17 at 19:55
12
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ (+1) I posted my answer and then saw yours. $\endgroup$ – robjohn Jul 22 '17 at 19:44
  • 2
    $\begingroup$ (+1) This solution might seem overly complicated, but generating function is a very powerful method in combinatorics and this is a nice example of how to apply it. $\endgroup$ – Wood Jul 22 '17 at 21:44
10
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
0
$\begingroup$

I've got a rather non-mathematical solution. First, simplify

$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5} = 25,\quad 1 \le x_i \le 6$$

using $y_i = x_i -1$ to

$$y_{1}+y_{2}+y_{3}+y_{4}+y_{5} = 20,\quad 0 \le y_i \le 5$$

and (just like the top answer) use the dual $z_i = 5 - y_i$ to get

$$z_{1}+z_{2}+z_{3}+z_{4}+z_{5} = 5,\quad 0 \le z_i \le 5$$

Note that I could drop the upper bound, but I don't care.

Let $f(i, n)$ be the number of possibilities how to obtain $n$ as sum of $i$ variables in to the range $0..5$. Obviously, for every $0 \le n \le 5$

$$f(1, n) = 1$$ $$f(2, n) = \sum_{j=0}^n\ f(1, n) \cdot f(1, n) = n+1$$ $$f(3, n) = \sum_{j=0}^n\ f(1, n) \cdot f(2, n) = \sum_{j=0}^n\ n+1 = \frac{(n+1)(n+2)}2$$ $$f(5, n) = \sum_{j=0}^n\ f(2, n) \cdot f(3, n)$$

Let $s(i)$ denote the sequence $f(i, 0), \dots, f(i, 5)$

$$s(1) = 1, 1, 1, 1, 1, 1$$ $$s(2) = 1, 2, 3, 4, 5, 6$$ $$s(3) = 1, 3, 6, 10, 15, 21$$

and compute the result as

$$1\cdot21 + 2\cdot15 + 3\cdot10 + 4\cdot6 + 5\cdot3 + 6\cdot1 = 126$$

Falling back to such a computation feels very non-mathematical (I could compute the sum symbolically, but I chose not to), but it's useful in case no closed form expression can be found or gets too complicated (just add some crazy condition and you're there). When this happens, then after some simplifications, the computer is your friend.

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