Number of throws where each face appears at least once.

41 Views Asked by At

Given $10$ distinct dice I want to know the number of throws where each one of the $6$ faces appears at least once.

First I approached the problem by puting all the $6$ faces and there are $\dfrac{10!}{(10-6)!}=151 200$ ways to do this, it remains to fill the remaining empty $4$ places with any way using the $6$ faces and there are $6^4$ ways to do this but the product gives a number that surpasses $6^{10}$ which is the number of all possible throws.

Then I looked at the complementary set, so the number of throws where the face $1$ does not appear is $5^{10}$ and similarly for the other faces, so the complementary set of throws contains $6*5^{10}$ hence the required number of throws is $6^{10}-6*5^{10}= 1 872 426$. Is it correct?

1

There are 1 best solutions below

0
On BEST ANSWER

Inclusion-exclusion will solve this if you are so inclined.

We recognize that there are $6^{10}$ ways to roll the dice if we don't care about missing faces and keep track of order in which dice are rolled.

We then try to remove from this count the number of ways we could roll who missed having a $1$, so we subtract $5^{10}$. We also subtract how many were missing a $2$, and a $3$ etc...

In doing so however, some outcomes were subtracted from our total multiple times when they should only have been subtracted once. For example, the outcome where we rolled $3,4,5,6,3,4,5,6,3,4$ both missed having $1$'s and missed having any $2$'s. That was subtracted twice rather than just once. In the other extreme, the outcome where we rolled nothing but $6$'s we accidentally subtracted from our count five times.

We correct this by continuing with inclusion-exclusion principle... adding back in the amount of ways we missed (at least) two numbers simultaneously, then subtracting again the number which missed three, adding back the number that missed four etc... for a final total of:

$$6^{10}-6\cdot 5^{10}+\binom{6}{2}\cdot 4^{10}-\binom{6}{3}\cdot 3^{10}+\binom{6}{4}\cdot 2^{10}-\binom{6}{5}\cdot 1^{10} = 16435440$$


This is such a common problem that new notation was invented to help make it easier to write the answer. Using Stirling Numbers of the Second Kind the answer will be written simply as:

$${10\brace 6}\cdot 6! = 16435440$$


As for why your first attempt failed, it is because you are incorrectly applying significance to whether something was a part of the "original six" versus a part of the extra. The outcome $1,2,3,4,5,6,1,2,3,4$ was counted once when you chose the first six positions with the numbers $1$ through $6$ and then individually filled the remaining... and was counted again when you first filled the last six positions with $1$ through $6$ and then followed by individually filling the beginning spots.