Associated Topics || Dr. Math Home || Search Dr. Math

Getting One of Each Number (1-6) Rolling N Dice

```
Date: 05/24/2001 at 13:58:10
From: Kevin Mayville
Subject: Probability of getting at least one of each number (1-6)
rolling N dice

I've been trying to determine some probabilities involving randomly
distributing items to a group of six people.  Certain of them, such as
the probability of someone getting M items out of N rolls or of the
items being divided evenly (with N a multiple of 6), were readily
solvable for me using binomial distribution. I'm having some
difficulty getting a handle on either a formula or a systematic
approach at determining the odds that each person gets at least one
item when N > 6. Attacking it in a manner such as doing combinations
like 123456XXXXXX (for N = 12) doesn't seem viable because the X's
aren't a separate group of results... it doesn't matter what they are
as far as the answer goes, but they affect the number of combinations.

Any ideas?
```

```
Date: 05/25/2001 at 21:25:57
From: Doctor Pat
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

Kevin,

If you are familiar with matrices, the Markov method is a good
approach, but it does need some calculation (I used my trusty TI-83).

Think of the seven states you can be in during the process if you roll
the dice (or assign the objects) one at a time. Each state corresponds
to the number of non-empty bins. Before you roll you are in state
zero, but after your first roll you will never be back to this state,
so we focus on the six remaining states and the eleven (or N-1)
remaining rolls.

At each level it is easy to determine the probability that you go to
the next state, and the probability you remain in your given state,
(all other states have probability zero for that transition - you
can't get from two bins occupied to four bins occupied in a single
assignment).

We express these transitions as a 6x6 probability matrix where each
row,column value (m,n) expresses the probability of going from state m
to state n on the next roll. The matrix looks like this:

1/6   5/6   0   0   0   0
0    1/3  2/3  0   0   0
0     0   1/2  1/2 0   0
0     0    0   2/3 1/3 0
0     0    0    0  5/6 1/6
0     0    0    0   0  1

The state 6,6 is absorbing because if six bins are occupied after any
roll, they will still be occupied after any subsequent roll.

The top row also represents the probability of being in any particular
state after two rolls (remember we took one roll to get in state one).

If we multiply this matrix times itself, it gives us the probability
of where we might be after three rolls, and again, the top row tells
us the probabilities of the state we will end up in after two rolls
starting from position one (three rolls from position zero).

These should match what you would get with a simple tree diagram of
the probabilities. For that line I got 1/36, 5/12, 5/9, 0, 0, 0  as we
would expect.

If you raise the original state matrix to the eleventh power (to find
the probabilities after 12 rolls in all) you get about 43% probability
of being in state 6 (six bins occupied). The actual value was 1654565/
3779136.

Hope that is of help to you.  Good luck.

- Doctor Pat, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/27/2001 at 16:24:38
From: Kevin J Mayville
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

Thanks, that's exactly what I was looking for (even though it means I
need to get a better calculator or at least a program that will
multiply matrices). I've been having a hard time convincing people
that even if random numbers are *unbiased*, that doesn't mean that the
final distribution will be fair or even approximately fair except in
the realm of large numbers.
```

```
Date: 05/28/2001 at 15:43:07
From: Doctor Anthony
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

The probability that all 6 numbers will have occurred after 12 rolls
of a die can be calculated as follows:

We find an expression for T(n,m) where this represents the number of
ways of placing n distinguishable objects at random into m
distinguishable boxes so that no box is empty. In our problem we have
n=12 balls and m=6 boxes.

The generating function for this number is [e^x - 1]^6  and we must
pick out the coefficient of x^12/12!. This is simply the usual
exponential generating function with the -1 there to ensure that no
box is empty.

The number of such arrangements is given by:

12!
------------------    where  n1 + n2 + n3 + n4 +n5 + n6 = 12
n1!n2!n3!n4!n5!n6!
with no n(i) = 0

and if we sum this for ALL possible solutions of n1+n2+n3+n4+n5+n6 =
12 and no n(i) = 0 we obtain the number of ways that 12 different
objects can be placed at random into 6 different boxes with no empty
boxes.

[e^x - 1]^6 = e^(6x) - C(6,1)e^(5x) + C(6,2)e^(4x) - C(6,3)e^(3x)
+ C(6,4)e^(2x) - C(6,5)e(x) + 1

We now pick out the terms in x^12

=  6^12/12! - 6(5^12/12!) + 15(4^12/12!) - 20(3^12/12!)
+ 15(2^12/12!) - 6(1^12/12!)

= (1/12!)[6^12 - 6(5^12) + 15(4^12) - 20(3^12) + 15(2^12) - 6]

= (1/12!)[953029440]

and so the coefficient of x^12/12! is  953029440

If you throw a die 12 times the total number of possible outcomes,
with 6 possibilities at each throw, is 6^12

So the required probability is  953029440/6^12  =  0.43781568

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/30/2001 at 16:50:12
From: Kevin J Mayville
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

Thanks for the help! Is there a straightforward way to generalize the
generating function for varying minimum numbers of items per box? I
experimented with (e^x - 2)^6, etc., and it didn't seem to give
accurate results. Do you know of any resources you could point me at
online for a good overview of this method so I don't end up sending
another email every time I decide to play around with this problem
some more?
```

```
Date: 05/30/2001 at 17:26:50
From: Doctor Anthony
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

If you want minimum numbers (say 2) in the boxes you can start by
putting one ball in each box and then distribute the remaining balls
using the method already described. There are so many variations to
these occupancy problems that you really require a good textbook on
combinatorics to guide you through the maze. A classic of this type is
_Applied Combinatorics_ by Fred S. Roberts.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/30/2001 at 18:06:12
From: Doctor Pat
Subject: Re: Probability of getting at least one of each number (1-6)
rolling N dice

Kevin,

This is not nearly as elegant as Dr. Anthony's exponential, but I
think an understandable approach would be to use polynomial generating
functions. I believe this will work, but you can check with some
simulation.

If you represent the possible number of balls in a bin by a polynomial
power of that number, and multiply all the possibilities out, you can
then look at the appropriate power to find the number of
permutations...

That is hard to understand, so a brief example. Suppose with the case
of 12 balls and four bins you want to know the probability of getting
at least two in each bin.. Then in each bin there may be as few as
two, and as many as six (if 2 are in each of three bins and six in
another)  Express the number of possible balls in one bin by
(x^2/2! + x^3/3!+x^4/4!+x^5/5!+x^6/6!) where x^2/2! is accounting for
the case of exactly two balls in the bin, x^3 for three, etc.

Now we raise this to the fourth power since there are four bins with
the same chances. We get a huge polynomial (24th power) but we are
looking only for the coefficient of x^12/12! as in Dr. Anthony's
solution. I got a little over 7.27 million ways for this.

Hope this helps. I'll be looking for the book Dr. Anthony recommended
too; his was a really elegant approach.

Good luck.

- Doctor Pat, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search