0
$\begingroup$

You roll $10$ dice. How many possible outcomes include the numbers $1$ to $6$?

It's essentially asking how many outcomes there are for 1 die to be 1, another to be 2, another to be 3, another to be 4, another to be 5, and another to be 6.

I know that we have $6 \cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 = 6!$ ways for 6 dice to contain 1-6, but I'm not sure about 10 dice. Thanks

$\endgroup$
  • $\begingroup$ This is a problem where you have to be very careful about not double-counting things. $\endgroup$ – Gregory Grant Feb 16 '16 at 1:21
  • $\begingroup$ Your interpretation is right. We are asked how many possible outcomes have at least one $1$ and at least one $2$ and so on. $\endgroup$ – André Nicolas Feb 16 '16 at 1:28
  • $\begingroup$ @AndréNicolas Alright, that's good. I'm not sure how to consider the other 4 dies though. $\endgroup$ – Robert MingHao Feb 16 '16 at 1:28
  • $\begingroup$ It is not even clear what is meant by outcomes. Are the dice distinguishable or not? If indistinguishable, it is plain Stars and Bars. If distinguishable, one can do cases or Inclusion/Exclusion, neither pleasant. $\endgroup$ – André Nicolas Feb 16 '16 at 1:34
  • $\begingroup$ Plural is "dice". Corrected. $\endgroup$ – GEdgar Feb 16 '16 at 1:38
3
$\begingroup$

You might try inclusion-exclusion. You want all possible sequences of ten numbers from $1$ through $6$ with repetition, except for the ones that have only five or fewer distinct numbers.

So we start with a set of sequences $S$ containing all $6^{10}$ possible sequences. But this includes, for example, $5^{10}$ sequences using only the numbers $1$ through $5$. Let $A_i$ be the set of all sequences of $10$ numbers from $1$ through $6$, excluding the number $i$. For example, $A_1$ consists of all sequences of the numbers $2$ through $6$.

The sequences we want are just the set $$S - \bigcup_{1\leq i \leq6} A_i.$$ The number of sequences is $$\left\lvert S - \bigcup_{1\leq i \leq6} A_i \right\rvert = \lvert S \rvert - \left\lvert\bigcup_{1\leq i \leq6} A_i \right\rvert.$$

To evaluate the last term, $\left\lvert\bigcup_{1\leq i \leq6} A_i \right\rvert,$ we can use the inclusion-exclusion principle. Since all the $A_i$ are the same size, all intersections of two distinct $A_i$ are the same size, etc., we can write this as \begin{split} \left\lvert\bigcup_{1\leq i \leq6} A_i \right\rvert =& \binom 61 \left|A_1\right| - \binom 62 \left|A_1\cap A_2\right| + \binom 63 \left|A_1\cap A_2\cap A_3\right| \\ &- \binom 64 \left|A_1\cap A_2\cap A_3\cap A_4\right| + \binom 65 \left|A_1\cap A_2\cap A_3\cap A_4\cap A_5\right| \\ &- \binom 66 \left|A_1\cap A_2\cap A_3\cap A_4\cap A_5\cap A_6\right| \end{split}

The last term is zero, since $A_1\cap A_2\cap A_3\cap A_4\cap A_5\cap A_6$ is the set of sequences of ten numbers from $1$ through $6$ that do not use any of the numbers $1$ through $6$; the empty set. The set $A_1\cap A_2\cap A_3\cap A_4\cap A_5$ is all sequences consisting of just the number $6$; $A_1\cap A_2\cap A_3\cap A_4$ is the sequences consisting of just the numbers $5$ and $6$; and so forth. In short, $$ \left\lvert\bigcup_{1\leq i \leq6} A_i \right\rvert = \binom 61 5^{10} - \binom 62 4^{10} + \binom 63 3^{10} - \binom 64 2^{10} + \binom 65 1^{10} $$

So the final answer is $$ 6^{10} - \binom 61 5^{10} + \binom 62 4^{10} - \binom 63 3^{10} + \binom 64 2^{10} - \binom 65 1^{10} $$

$\endgroup$
5
$\begingroup$

Use Inclusion and Exclusion. All the ways to select at most 6 distinct faces, minus all the ways to select at most 5 of the 6, plus all the ways to select at most 4 four of the six, minus...

$$\dbinom 6 6~6^{10} - \dbinom 6 5~ 5^{10} + \dbinom 6 4~ 4^{10} - \dbinom 6 3~ 3^{10} + \dbinom 6 2~ 2^{10}-\dbinom 6 1 ~1^{10} + \dbinom 6 0 ~0^{10}$$

$\endgroup$
  • $\begingroup$ Why would this work? $\endgroup$ – Robert MingHao Feb 16 '16 at 2:17
  • $\begingroup$ I somehow missed seeing this get posted while I wrote up my answer--partly because I wrote more details, partly because I messed up the first attempt at an answer and had to rewrite it. At least it's reassuring the result came out the same in the end. $\endgroup$ – David K Feb 16 '16 at 2:38
  • $\begingroup$ @RobertMingHao P.I.E. Nested exclusion of over counted intersections eliminates the overcounting. See David K's answer. $\endgroup$ – Graham Kemp Feb 16 '16 at 3:01
  • $\begingroup$ Short and sweet. (+1) $\endgroup$ – true blue anil Feb 16 '16 at 19:22
1
$\begingroup$

Here's one way to do it. May not be the most efficient way, but it should work. If there's some slick way to do this quickly that I don't know of, then I apologize and I'll be happy to delete this.

Break it down by how many of the numbers are duplicated. You can have up to five of any fixed number and if you have five you'd have to have exactly one each of the other five.

$5+1+1+1+1+1$

In this case choose the one to be duplicated in six ways. Choose the five dice that will be equal to that number in $10\choose5$ ways. The other five dice can be assigned to the other five numbers in $5!$ ways. So this accounts for $6\cdot{10\choose5}\cdot5!$ ways.

Now if there are four duplicates of one number, one other number would have to be duplicated twice and the other four just once.

$4+2+1+1+1+1$

In this case there is one number duplicated four times and another duplicated twice. Choose the number to be duplicated four times in six ways. For each way choose the other number to be duplicated twice in five ways. Choose the four dice to be assigned the first number in $10\choose4$ ways and for each choose the two to be assigned to the second number in $6\choose2$ ways. The other four numbers are assigned in $4!$ ways. So this accounts for $6\cdot5\cdot{10\choose4}\cdot{6\choose2}\cdot 4!$ ways.

I believe there are only three other possibilities:

$3+3+1+1+1+1$

Choose the two to be duplicated in $6\choose2$ ways. For each choose the six dice to be duplicates of one of these, in $10\choose6$ ways, and for each of those six dice choose which three to duplicate with one number and which three to duplicate with the other, in $6\choose3$ ways. The other four dice can be placed in $4!$ ways. So this accounts for $4!{6\choose2}{10\choose6}{6\choose3}$ ways.

The other two ways are

$3+2+2+1+1+1$

$2+2+2+2+1+1$

So for each one you need to count the total number, doing a similar calculation as above.

Then total all of these five numbers and divide by $6^{10}$ which is the total number of ways to roll ten dice.

$\endgroup$
1
$\begingroup$

I like to reduce the case approach to two multinomial coefficients for [choose] $\times$ [place]
to make it more mechanical and thus less error prone.

$5-1-1-1-1-1: \dbinom6{1,5}\dbinom{10}{5,1,1,1,1,1}$

$4-2-1-1-1-1: \dbinom6{1,1,4}\dbinom{10}{4,2,1,1,1,1}$

$3-3-1-1-1-1: \dbinom6{2,4}\dbinom{10}{3,3,1,1,1,1}$

$3-2-2-1-1-1: \dbinom6{1,2,3}\dbinom{10}{3,2,2,1,1,1}$

$2-2-2-2-1-1: \dbinom6{4,2}\dbinom{10}{2,2,2,2,1,1}$

Add up and divide by $6^{10}$

PS

Or you might like to write it as [choose] $\times$ [permute], viz.

$5-1-1-1-1-1: \dbinom6{1,5}\times\dfrac{10!}{5!}$

$4-2-1-1-1-1: \dbinom6{1,1,4}\times\dfrac{10!}{4!2!}$

$3-3-1-1-1-1: \dbinom6{2,4}\times\dfrac{10!}{3!3!}$

$3-2-2-1-1-1: \dbinom6{1,2,3}\times\dfrac{10}{3!2!2!}$

$2-2-2-2-1-1: \dbinom6{4,2}\times\dfrac{10!}{2!2!2!2!}$

$\endgroup$
-4
$\begingroup$

Based on the comments below, I try a different approach. I consider $1-$the number of cases where all numbers are not there.

Choose 5 out of 6 numbers. Each dice can be any number = $5^{10}$

So, the total number of ways is $6^{10} - 6*5^{10}$

$\endgroup$
  • 2
    $\begingroup$ Double Counting! Suppose you pick the first die and its a one, there's another one in the six you didn't pick. Suppose you picked that place, and its a one, and the one among the six you didn't pick is in first place. You've counted these at least twice. $\endgroup$ – Graham Kemp Feb 16 '16 at 1:37
  • $\begingroup$ This method double counts just as I warned above in the comments. $\endgroup$ – Gregory Grant Feb 16 '16 at 1:37
  • $\begingroup$ @RobertMingHao Be careful this is a wrong solution, it double counts many possibilities. You should convince yourself of why this is wrong there's an important lesson here. $\endgroup$ – Gregory Grant Feb 16 '16 at 1:38
  • 1
    $\begingroup$ Beside the double counting, this answer says $10C_4$ in one place and $6C_4$ later. (Double counting for example because choose the first four dice and make them all 6, then let the others be 6,5,4,3,2,1, is the same outcome as choose the four dice after the first and make them all 6, then let the others be 6,5,4,3,2,1.) $\endgroup$ – David K Feb 16 '16 at 1:42
  • $\begingroup$ @GrahamKemp I edited.. Please check and tell if I am again wrong. $\endgroup$ – Win Vineeth Feb 16 '16 at 1:47

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.