1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ok I got a bit confised again. why "all such results are sure to violate the constraint"? "pre-placing 6 in a bin" means "getting 6 on a dice" right? That is allowed right? We can have 17 with one 6: {6,5,5,1} and with two 6s: {6,6,3,2}. What I am missing? $\endgroup$ – anir123 Feb 17 '16 at 11:51
  • 1
    $\begingroup$ You have pre-placed $6$. When you roll, the minimum you can get is $1$, i.e. a total of $7$ $\endgroup$ – true blue anil Feb 17 '16 at 12:59
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ let me prove myself poor in maths...how is $−y_1−y_2−y_3−y_4=-7$, in the line above equation (2) Shouldn't it be $−y_1−y_2−y_3−y_4=-17$ ? $\endgroup$ – anir123 Feb 14 '16 at 12:56
  • $\begingroup$ I made an error in the preceding step, now corrected. Since I was substituting $6 - y_k$ for $x_k$, $1 \leq k \leq 4$, in equation 1, I should have obtained $6 - y_1 + 6 - y_2 + 6 - y_3 + 6 - y_4 = 17$. $\endgroup$ – N. F. Taussig Feb 14 '16 at 13:02
  • $\begingroup$ Not getting the point behind: we must exclude those solutions of equation 2 in which one or more of the $y_k$'s exceeds 5. Since $2⋅5=10>7$, at most one of the $y_k$'s can exceed 5. Q(1) Why exclude? To ensure non of $y_i$ is zero? Q(2) You said "exceed 5". So that must be 6 or more. Then why you pointed out $2⋅5=10>7$? In fact it can be $2.4=8>7$, though I dont get why we are doing that as in Q(1) Q(3) You said "exclude solutions having one or more of $y_k$'s exceeding $5$" and then said "at most one of the $y_k$'s can exceed $5$".Not allowing one more disallows at least one $\endgroup$ – anir123 Feb 14 '16 at 14:35
  • $\begingroup$ ^sorry for being slow at understanding your solution $\endgroup$ – anir123 Feb 14 '16 at 14:58
  • $\begingroup$ I defined $y_k = 6 - x_k$. Since $x_k$ satisfies the inequalities $1 \leq x_k \leq 6$ and $x_k = 6 - y_k$, we have $$1 \leq 6 - y_k \leq 6 \iff -1 \geq y_k - 6 \geq -6 \iff 5 \geq y_k \geq 0$$ Thus, the condition that $x_k$ is a positive integer that is at most $6$ imposes the condition that $y_k$ is a non-negative integer that is at most $5$. Therefore, any solution in which one or more of the variables exceeds $5$ is not valid. Since the sum of the $y_k$'s is $7$, it is not possible for two or more of the $y_k$'s to exceed $5$ since $2 \cot 6 = 12$ and still satisfy equation 2. $\endgroup$ – N. F. Taussig Feb 14 '16 at 15:07
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ bro I "placed separator anywhere" for second problem not first one (the one which is the concern of this post), and I dont think I asked for probability anywhere. $\endgroup$ – anir123 Feb 14 '16 at 12:33
  • $\begingroup$ Poor wording from me, fixed it $\endgroup$ – AnalysisStudent0414 Feb 14 '16 at 12:34

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.