Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

" When one red and blue dice are rolled, how many ways are there to get a sum that is less than 6 ? "

I am trying to manipulate factorial, Permutation and Combination, but I can't arrive at a solution besides listing down the possibilities.

share|improve this question

3 Answers 3

Here is another method. Let's assume, the first rolled dice gave us $x$. Then for the other one there are $5-x$ possibilities. So the number of such cases would be $\sum_{x=1}^{5}{(5-x)}=5*5-\sum_{x=1}^{5}{x}=25-5*6/2=10$.

share|improve this answer
    
You may need to state explicitly why you do not have $x=6$ in the sum, even though it may be obvious. –  Henry Aug 5 '12 at 9:46

Since you want a combinatorial approach to solving this answer, let's extend the question to $n$ dice adding up to at most $s$.

We are looking for the number of solutions to $$ a_1 + a_2 + \cdots + a_n \le s \tag{1}$$ where $a_i$ shall represent the value of the $i$th die and therefore carry the restriction $1 \le a_i \le 6$.

By placing a lower limit of $1$ on each $a_i$, what we really have is $$ (b_1 + 1) + (b_2 + 1) + \cdots + (b_n + 1) \le s \tag{2} $$ where $b_i + 1 = a_i$. We get the following equivalent formulations: $$ b_1 + b_2 + \cdots + b_n \le s - n \tag{3} $$ $$ 1 \le b_i + 1 \le 6 $$ $$ 0 \le b_i \le 5 \tag{4}$$

We seek the number of solutions to $(3)$. Because of the $\le$ sign in $(3)$, however, the number of solutions is equal to the sum of the number of solutions to $$ b_1 + b_2 + \cdots + b_n = k, \qquad \mbox{for } k=0,1,2,\ldots,s-n \tag{5}$$ Finding the solutions for each $k$ in $(5)$ will get unwieldy for large $n$, so a better approach is required. Here, we introduce a dummy variable $d$ that will act as an elastic filler; whatever the sum $\sum_{i=1}^n b_i$ evaluates to, $d$ will assume a value such that $$ b_1 + b_2 + \cdots + b_n + d = s - n \tag{6}$$ which can easily be solved using the Stars and Bars technique. For $n + 1$ partitions, we need $n$ bars to partition the $s - n$ stars: $$\binom{s - n + n}{n} = \binom{s}{n} \tag{7}$$

Because we haven't accounted for the upper limit in $(6)$, solutions where, e.g., $b_i = 6 \Rightarrow a_i = 7$, are counted in $(7)$. Our focus now is on the upper limit of $b_i$ in $(6)$ as specified by $(4)$. The approach is to find the number of solutions that contain at least one $b_i$ that exceeds its upper limit. Subtracting this value from $(7)$ will yield the answer to the problem.

Let $A_1$ denote the set of solutions to $(6)$ in which $b_1$ has exceeded the upper limit. That is, $A_1$ is the set of solutions to $$ b_1 + b_2 + \cdots + b_n + d = s - n, \qquad b_1 > 5 \tag{8}$$ $b_1 > 5 \Rightarrow 6 \le b_1$, so we have a new lower limit on $b_1$. Adjusting $(8)$ accordingly, we have $$ b_1 + b_2 + \cdots + b_n + d = s - n - 6 \tag{9}$$ which holds the solutions in $A_1$.

Because of the symmetry of $(9)$ and the fact that each $b_i$ has the same upper and lower bounds, the solutions to $(9)$ are in fact the solutions in $A_i$ where $b_i > 5$, for each $i = 1, 2, \ldots, n$. As such, we wish to find the number of solutions in the union of each $A_i$, and that can be found using the Principle of Inclusion and Exclusion to avoid over-counting: $$ |A_1 \cup A_2 \cup \cdots \cup A_n| = \left|\bigcup_{i=1}^n A_i \right| $$ $$ = \sum |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| + \cdots + \left| \bigcap_{i=1}^n A_i \right| \tag{10}$$

For the first summation, since there are $$\binom{s - n - 6 = n}{n} = \binom{s - 6}{n}$$ solutions to each $A_i$ and $\binom{n}{1}$ ways to select an $A_i$, the sum is $$ \sum |A_i| = \binom{n}{1}\binom{s - 6}{n}.$$

By the same token, $A_i \cap A_j$ denote the solutions to $(6)$ where both $b_i$ and $b_j$ have passed their upper limits. These are the solutions to $$ b_1 + b_2 + \cdots + b_n + d = s - n, \qquad b_i, b_j > 5 \mbox{ for unique } i, j \tag{11}$$ As with $(8)$, both $b_i$ and $b_j$ greater than $5$ implies that $6 \le b_i$ and $6 \le b_j$. This yields $$ b_1 + b_2 + \cdots + b_n + d = s - n - 12 \tag{12}$$ The number of solutions to $(11)$, multiplied by the number of ways to intersect two unique $A_i$ gives $$ \sum_{i<j} |A_i \cap A_j| = \binom{n}{2}\binom{s - 12}{n} \tag{13}$$

Following the pattern, $(10)$ becomes $$ \bigcup_{i=1}^n A_i = \binom{n}{1}\binom{s - 6}{n} - \binom{n}{2}\binom{s - 12}{n} + \cdots + (-1)^{n+1}\binom{n}{n}\binom{s - 6n}{n} $$ $$ \bigcup_{i=1}^n A_i = \sum_{i=1} {(-1)^{i+1}\binom{n}{i}\binom{s - 6i}{n}} \tag{14}$$

It is important to note that $\binom{s - 6i}{n}$ is only valid for $i$ in $$ b_1 + b_2 + \cdots + b_n + d = s - n - 6i \tag{15}$$ such that $s - n - 6i\ge 0$ because $(15)$ would otherwise not have any solutions. So the upper limit on $i$ is given by $$ i \le \left\lfloor\frac{s - n}{6}\right\rfloor \tag{16} $$

So $(14)$ becomes $$ \bigcup_{i=1}^n A_i = \sum_{i=1}^{\left\lfloor\frac{s - n}{6}\right\rfloor} {(-1)^{i+1}\binom{n}{i}\binom{s - 6i}{n}} \tag{17}$$

Subtracting from $(7)$ gives $$\mbox{Number of solutions to (3)} = \binom{s}{n} - \sum_{i=1}^{\left\lfloor\frac{s - n}{6}\right\rfloor} {(-1)^{i+1}\binom{n}{i}\binom{s - 6i}{n}} \tag{18}$$ $$ = \binom{s}{n} + \sum_{i=1}^{\left\lfloor\frac{s - n}{6}\right\rfloor} {(-1)^{i}\binom{n}{i}\binom{s - 6i}{n}} \tag{19} $$

So for $n=4$ dice, and a maximum sum of $s = 15$, we have $$ \binom{15}{4} + \sum_{i=1}^{\left\lfloor\frac{11}{6}\right\rfloor} {(-1)^{i}\binom{4}{i}\binom{15 - 6i}{n}} = 861$$

and a short program to verify the formula yields:

>>> dice = range(1, 6 + 1)
>>> len([(a, b, c, d) for a in dice for b in dice
...             for c in dice for d in dice if a + b + c + d <= 15])
861
share|improve this answer

Listing and counting is the best way. But the following idea is useful elsewhere. We have $3$ kids, Red, Blue, and Black. We want to distribute $6$ identical candies between them, so that everybody gets at least one candy. Imagine setting out the $6$ candies in a row, with a little gap between candies. We will insert $2$ separators in the $5$ gaps between candies, no more than one separator per gap.

Red will get all the candies from the left end to the first separator. Blue will get all the candies between the two separators. And Black will get the rest.

There are exactly as many ways to distribute the candies as there are ways for the red die and the blue die to add up to $5$ or less. And the number of ways to insert the separators is $\binom{5}{2}$ (five gaps, and we must choose two of these to insert a separator into).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.