Xrfgtjtk

I am trying to determine the number of ways two dice can be rolled to have a sum of 8. This question can be easily brute-forced, but I want to use a technique that can be applied to similar questions that cannot be brute-forced so easily.

My solution was as follows,
$$x_1 +x_2 = 8, x_1, x_2 geq 1$$
$$x_1+1+x_2+1 = 8 rightarrow x_1+x_2 =6$$
Now I can use the stars and bars method.
So $C(6 +(2-1), (2-1))$ should be the answer, which is equal to $7$. But when I brute-forced this question, I only found $5$ solutions. What did I do wrong?

Normally if I wanted to find, say for example, the number of integer solutions to $x_1+x_2+x_3 = 12, x_i geq 0$, I would apply the same method and do $C(12+(3-1), (3-1))$. What am I doing wrong?

You stated that you found that there are exactly $5$ solutions by listing all the possibilities, so I will assume you are considering six-sided dice.

What you have failed to do is account for the fact that the largest number a six-sided die can display is $6$.

If two six-sided dice are rolled, in how many ways can the numbers on the top faces of the dice sum to $8$?

Suppose we roll a blue die and a green die. Let $x_1$, $x_2$ denote, respectively, the numbers on the top face of the blue die and top face of the green die. Then
$$x_1 + x_2 = 8 tag{1}$$
where $1 leq x_1, x_2 leq 6$.

You opted to convert this to a problem in the nonnegative integers, so let's let $x_1' = x_1 - 1$ and $x_2' = x_2 - 1$. Since $x_1$ and $x_2$ are positive integers, $x_1'$ and $x_2'$ are nonnegative integers. Substituting $x_1' + 1$ for $x_1$ and $x_2' + 1$ for $x_2$ in equation 1 and simplifying yields
$$x_1' + x_2' = 6 tag{2}$$
Since equation 1 is an equation in positive integers not exceeding $6$, equation 2 is an equation in nonnegative integers not exceeding $5$.

Without that restriction, a solution of equation 2 corresponds to the placement of one addition sign in a row of six ones. For instance,
$$1 1 + 1 1 1 1$$
corresponds to the solution $x_1' = 2$ and $x_2' = 4$. The number of such solutions is
$$binom{6 + 2 - 1}{2 - 1} = binom{7}{1} = 7$$
since we must choose which of the seven positions required for six ones and one addition sign will be filled with an addition sign.

From these, we must subtract those solutions in which one of the variables exceeds $5$.

There are two ways to choose which variable violates the restriction that $x_1', x_2' leq 5$. If a variable does violate that restriction, it must be equal to $6$ and the other must be equal to $0$, so there is only one possible solution of equation 2 for each variable that could violate the restriction that a variable cannot exceed $5$. Since there are two such variables, there are two solutions of equation 2 in which an upper bound is violated.

Hence, the number of possible ways for the numbers on the top faces of two six-sided dice to have a sum of $8$ is
$$binom{7}{1} - binom{2}{1} = 7 - 2 = 5$$

Hint: You have six choices for the first die, however if you roll a $1$ on the first die then no matter what you roll on the second die you cannot get to $8$. Thus, we want $x_1,x_2$ such that $x_1+x_2=8$ and $2leq x_1,x_2leq 6$.

Your sum count is wrong because you are including the cases where some of the $x_i>6.$ For example, $7+3+2=12,$ but you don't want to count that case.

Summary:

The number of ways of getting the sum $S$ from rolling $k$ fair $n$-sided dice labeled $1$ to $n$ is:
$$sum_{i=0}^{k}(-1)^ibinom{k}{i}binom{S-in-1}{k-1}$$
You have to be careful evalating this, because $binom{m}{j}$ is not a polynomial in $m$ for fixed $j$, since it is $0$ when $m<j.$

A trick to make it easier is that you can replace any $S$ with $(n+1)k-S$ and get the same count. So you can always use $Sleq frac{(n+1)k}{2}$, in which case you can ignore terms with $i>frac{k+1}{2}$ since then $binom{S-in-1}{k-1}=0.$

Longer:

This is a case for either generating functions or an inclusion-exclusion argument.

The generating approach applied to the sum of two fair six-sided dice is to compute the coefficients of $x^8$ in:

$$(x+x^2+x^3+cdots + x^6)^2$$

or the coefficient of $x^6$ in:

$$(1+x+cdots+x^5)^2$$

Now, this might seem harder, but it isn't, because $1+x+cdots+x^5=frac{1-x^6}{1-x}$ So you are seeking the coefficient if $x^6$ in:

$$(1-x^6)^2frac{1}{(1-x)^2}tag{1}=(1-2x^6+x^{12})frac{1}{(1-x)^2}$$

And we have the general result:

$$frac{1}{(1-x)^{k}}=sum_{m=0}^{infty} binom{m+k-1}{k-1}x^m tag{2}$$

So when $k=2$ you get:

$$frac{1}{(1-x)^2}=sum_{m=0}^{infty}(m+1)x^m$$

Multiplying by $(1-x^6)^2=1-2x^6+x^{12}$ this means the coefficient of $x^j$ in $(1)$ is:

$$binom{j+1}{1}-2binom{j-5}{1}+binom{j-11}{1}$$

We can't replace $binom{n}{1}$ with $n$ because we need to $binom{n}1=0$ when $n<1.$ The term $binom{j-11}{1}$ is only ever really used to "zero out" the cases where $binom{j+1}{1}-2binom{j-5}{1}$ is negative.

When seeking the number of ways to get a sum of $8$, we use $j=8-2=6$ this is $7-2=5.$

When the sum we are seeking, $S,$ is between $2$ and $7$, inclusive, this formula gives us a count of:

$$S-1$$

because the term $binom{S-7}{1}=0$ when $Sleq 7.$

and when $7<Sleq 12$ this number of ways is:

$$S-1 - 2(S-7)=13-S$$

When $S>12$ all the sum is:

$$(S-1)-2(S-7)+(S-13)=0$$

And when $S<2$ all the terms are zero.

More generally, if you are rolling a set of $k$ $n$-sided dice, you get,via $(2)$, then the number of ways to get a total of $S$ is the coefficient of $x^{S-k}$ in:

$$(1-x^n)^ksum_{m=0}^{infty}binom{m+k-1}{k-1}x^m$$

Thus we get that the number of ways to get a sum $S$ from $k$ $n$-sided dice is: $$sum_{i=0}^{k}(-1)^ibinom{k}{i}binom{S-in-1}{k-1}$$

You can also prove this formula using inclusion-exclusion, rather than using generating functions.

Example: when throwing three eight-sided dice, the number of ways to get a sum of $S$ is:

$$binom{S-1}{2}-3binom{S-9}{2}+3binom{S-17}{2}-binom{S-25}{2}$$

Which yields:
$$begin{cases}
0&S<3\
frac{(S-1)(S-2)}{2}&3leq S<11\
27S-S^2-134&11leq S<19\
frac{(25-S)(26-S)}{2}&19leq Sleq 24\
0&25leq S
end{cases}
$$

You also have, in general, the value for $S$ and $(n+1)k-S$ should be equal. This means that you can always solve for $S$ by using at most the first $frac{k+1}{2}$ terms of the sum, with the other terms zero.

When dealing with differently-sided dice, you get the same kind of result, but the numerator is different.

For example, a four- and six-sided die rolled together gives you:

$$x^2(1-x^4)(1-x^6)sum_{m=0}^{infty}binom{m+1}{1}x^m$$

Then the coefficient of $x^S$ in this is:

$$binom{S-1}{1}-binom{S-5}{1}-binom{S-7}{1}+binom{S-11}{1}$$