Number of ways to get 17 by rolling dice 4 times (with combinatorial argument)

Question

A dice is rolled four times. In how many ways we can get total of 17?

We can solve this by finding coefficient of $x^{17}$ in the ordinary enumerator $(x+x^2+x^3+x^4+x^5+x^6)^4$. But I feel this requires little bit more effort.

We can directly solve similar problem like:

In how many ways we can select four positive non zero integers having total of 17

as $\binom{17-1}{4-1}$ (since we have to select 3 positions out of 16 separating 17 objects for them to be divided in 4 groups). This way we dont have to go for enumerator. How solution to the original problem can be obtained with such combinatorial argument instead of using generating function?

Or may be I can rephrase the problem as what is the direct formula for such question where we have upper limit on number of objects of particular type to be selected (6 in case of dice) to get particular sum. When their is no upper limit the formula turns out to be $\binom{n-1}{r-1}$.

Note: Second problem can be solved by finding coefficient of $x^{17}$ in $(x+x^2+x^3+x^4+...)^4$, the approach which I dont want to follow for the first problem.

Answer 1

Using the "balls and bins" analogy, what we can do is to pre-place $6$ in one or more of the "bins". All such results are sure to violate the constraint, and applying inclusion-exclusion to exclude them, we arrive at the desired answer.

For the particular example, $\binom{16}{3} - \binom41\binom{10}{3} + \binom42\binom43 = 104$

If you want to generalize the formula, if L is the upper limit ($6$ for dice),

$$F(n,r,L) = \sum_{j=0}^J(-1)^j \binom{r}{j}\binom{n-1-Lj}{r-1}, J = \left\lfloor\frac{n-r}{L}\right\rfloor$$

Answer 2

Your solution to the second problem doesn't translate well to the first one, since a die goes from $1$ to $6$ so the separators can't be placed everywhere.

You can, however, do something else. Ordering from big to small, the possible combinations are $$6641, 6632, 6551, 6542, 6533, 6443, 5552, 5543, 5444$$

Now,
$6542$ has $4! = 24$ permutations
$6641, 6632, 6551, 6533, 6443, 5543$ have $\frac{4!}{2!} = 12$ permutations each
and $5552, 5444$ have $\frac{4!}{3!} = 4$ permutations each

so the total number of occurrencies is $$24+12\cdot 6 +4\cdot 2 = 24+72+8 = 104$$.

Answer 3

Let $x_k$ be the outcome of the $k$th roll. Then we want the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 17 \tag{1}$$ in the positive integers with the restriction that $x_k \leq 6$ for $1 \leq k \leq 4$.

Let $y_k = 6 - x_k$ for $1 \leq k \leq 4$. Then each $y_k$ is a non-negative integer satisfying $0 \leq y_k \leq 5$. Substituting $6 - y_k$ for $x_k$, $1 \leq k \leq 4$, in equation 1 yields \begin{align*} 6 - y_1 + 6 - y_2 + 6 - y_3 + 6 - y_4 & = 17\\ -y_1 - y_2 - y_3 - y_4 & = -7\\ y_1 + y_2 + y_3 + y_4 & = 7 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers. A particular solution of equation 2 corresponds to the placement of three addition signs in a row of seven ones. For example, $$1 1 + 1 1 1 + 1 1 +$$ corresponds to the solution $y_1 = 2$, $y_2 = 3$, $y_3 = 2$, and $y_4 = 0$, while $$1 + 1 1 + 1 1 1 + 1$$ corresponds to the solution $y_1 = 1$, $y_2 = 2$, $y_3 = 3$, and $y_4 = 1$. Thus, the number of solutions of equation 2 is the number of ways three addition signs can be inserted into a row of seven ones, which is $$\binom{7 + 3}{3} = \binom{10}{3}$$ since we must choose which three of the ten symbols (seven ones and three addition signs) will be addition signs.

However, we must exclude those solutions of equation 2 in which one or more of the $y_k$'s exceeds $5$. Since $2 \cdot 6 = 12 > 7$, at most one of the $y_k$'s can exceed $5$.

Suppose $y_1 > 5$. Let $z_1 = y_1 - 6$. Then $z_1$ is a non-negative integer. Substituting $z_1 + 6$ for $y_1$ in equation 2 yields \begin{align*} z_1 + 6 + y_2 + y_3 + y_4 & = 7\\ z_1 + y_2 + y_3 + y_4 & = 1 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers with $4$ solutions. By symmetry, any of the four variables could have exceeded $5$ in equation 2. Thus, the number of solutions of equation 2 in which one of the variables exceeds $5$ is $$\binom{4}{1} \cdot \binom{4}{1}$$ Hence, the number of ways to obtain a sum of $17$ with four rolls of a six-sided die is $$\binom{10}{3} - \binom{4}{1}^2$$