ENUMERATING COIN AND DICE THROWS
20031108 Mark Jason Dominus
mjd@plover.com
Here's how to count the number of different ways of rolling a certain
pattern of numbers with a certain number of dice.
1. Decide how many dice you'll be rolling. Let's call this number N.
2. Now enumerate all the different patterns. When N is 3, the
patterns are
AAA
AAB
ABC
and when N is 5, they are
AAAAA
AAAAB
AAABB
AAABC
AABBC
AABCD
ABCDE
This may be the trickiest part of the whole process, or it may be the
easiest, depending on what is already in your head. I will describe
an algorithm for listing all the patterns, but to avoid cluttering the
rest of the discussion, I have put it at the bottom of this message.
3. For each pattern, count the number of A's, the number of B's, and
so on, and write down the numbers:
red
AAAAA 5
AAAAB 4 1
AAABB 3 2
AAABC 3 1 1
AABBC 2 2 1
AABCD 2 1 1 1
ABCDE 1 1 1 1 1
Let's call these the red numbers.
4. For each pattern, count the number of 1's, the number of 2's, and
so on, among the red numbers, and write down the counts:
red blue
AAAAA 5 1
AAAAB 4 1 1 1
AAABB 3 2 1 1
AAABC 3 1 1 1 2
AABBC 2 2 1 2 1
AABCD 2 1 1 1 1 3
ABCDE 1 1 1 1 1 5
Let's call these the blue numbers.
5. Now we are going to calculate how many ways there are of assigning
numbers on the dice (1, 2, 3, 4, 5, or 6 pips) to the letters A, B, C,
etc., for each pattern. The rule is simple: let 'b' be the sum of the
blue numbers. Then the total number of ways of assigning letters to
die faces, which we'll call 'g', is:
b g
1 6 = 6
2 6*5 = 30
3 6*5*4 = 120
4 6*5*4*3 = 360
5 6*5*4*3*2 = 720
6 6*5*4*3*2*1 = 720
7 6*5*4*3*2*1*0 = 0
8 6*5*4*3*2*1*0*-1 = 0
... ... = 0
Note that if the sum 'b' is larger than 6, then the product 'g' will
contain a 0 term, and so will be 0. As a result, if you are throwing
more than 6 dice, the method will calculate that there are 0 ways of
throwing a pattern like ABCDEFG that requires 7 or more different
numbers to show.
Let's call these 'g' numbers the green numbers. Write them down next
to the red and blue numbers.
red blue green
AAAAA 5 1 6
AAAAB 4 1 1 1 30
AAABB 3 2 1 1 30
AAABC 3 1 1 1 2 120
AABBC 2 2 1 2 1 120
AABCD 2 1 1 1 1 3 360
ABCDE 1 1 1 1 1 5 720
If you want to do the calculation for dice with other than 6 sides,
this is the only thing that will change. For 8-sided dice, the green
numbers will be 8, 8*7, 8*7*6, etc., instead of 6, 6*5, 6*5*4, etc.,
in the obvious way. For 2-sided dice (coins), they will be 2, 2*1,
2*1*0, etc. Everything else is just the same.
6. Recall that the notation n! means n * n-1 * n-2 * ... * 3 * 2 * 1.
For example, 3! = 3*2*1 = 6 and 6! = 6*5*4*3*2*1 = 720.
Calculate r! for every red number r and b! for every blue number b.
Multiply the r!'s together; let's say this product is R.
Multiply the b!'s together; let's say this product is B.
Write down these products R and B:
red blue green R B
AAAAA 5 1 6 120 1
AAAAB 4 1 1 1 30 24 1
AAABB 3 2 1 1 30 12 1
AAABC 3 1 1 1 2 120 6 2
AABBC 2 2 1 2 1 120 4 2
AABCD 2 1 1 1 1 3 360 2 6
ABCDE 1 1 1 1 1 5 720 1 120
For example, the R number for pattern AAABC is 3! * 1! * 1! =
3*2*1 * 1 * 1 = 6.
7. Calculate N! * green / (R * B) for each pattern. (Remember N is
the number of dice; in this example N is 5, so N! is 120.)
For example, for the pattern AAABC, we calculate 120 * 120 / (6 * 2) =
1200. It so happens that R*B always divides into N! evenly, so usualy
the arithmetic is simplest if you divide N! by R*B and then multiply
by green.
This number is the total number of ways of rolling each pattern; it is
the final answer.
red blue green R B total
AAAAA 5 1 6 120 1 6
AAAAB 4 1 1 1 30 24 1 150
AAABB 3 2 1 1 30 12 1 300
AAABC 3 1 1 1 2 120 6 2 1200
AABBC 2 2 1 2 1 120 4 2 1800
AABCD 2 1 1 1 1 3 360 2 6 3600
ABCDE 1 1 1 1 1 5 720 1 120 720
8. Check your arithmetic. Add up the numbers in the 'total' column.
They should add up to 6^N. Here N is 5, so they should add up to 6^5
= 7776. (For 8-sided dice, the total will be 8^N; for 2-sided dice
the total will be 2^N.)
EXAMPLE: 3 DICE
Let's do a small example: 3 dice of 6 sides. First we enumerate the
patterns. There are only 3 patterns:
AAA
AAB
ABC
To get the red numbers we count the number of appearances of each
letter:
red
AAA 3
AAB 2 1
ABC 1 1 1
To get the blue numbers we count the number of appearances of each red
number:
red blue
AAA 3 1
AAB 2 1 1 1
ABC 1 1 1 3
The green numbers that correspond to the blue sums 1, 2, and 3 are 6, 6*5 =
30, and 6*5*4 = 120.
red blue green
AAA 3 1 6
AAB 2 1 1 1 30
ABC 1 1 1 3 120
To calculate R, we calculate r! for each red number and then multiply
the r!'s together.
To calculate B, we calculate b! for each red number and then multiply
the b!'s together.
red blue green R B
AAA 3 1 6 6 1
AAB 2 1 1 1 30 2 1
ABC 1 1 1 3 120 1 6
The totals are 3! * green / (R * B):
red blue green R B total
AAA 3 1 6 6 1 6
AAB 2 1 1 1 30 2 1 90
ABC 1 1 1 3 120 1 6 120
The numbers in the 'total' column should add to 6^3 = 216. They do,
so everything checks out. There are 6 ways of rolling 3 of a kind, 90
ways of rolling a pair, and 120 ways of rolling no pair.
To compute the probabilities, just divide the totals by 6^N. In this
example, 6^N = 216. The probability of rolling 3 of a kind is 6/216 =
2.78%. The probability of rolling a pair is 90/216 = 41.67%. The
probability of rolling no pair is 120/216 = 55.56%.
EXAMPLE: 5 COINS
Let's do one more example. This time instead of rolling dice, let's
flip 5 coins.
First we enumerate the patterns.
AAAAA
AAAAB
AAABB
AAABC
AABBC
AABCD
ABCDE
Why did I include patterns like AAABC that obvious can't come up with
coins? Just to show that it doesn't matter. This method will
calculate a 0 probability of throwing the pattern AAABC with 5 coins.
The red and blue numbers are the same as for the dice:
red blue
AAAAA 5 1
AAAAB 4 1 1 1
AAABB 3 2 1 1
AAABC 3 1 1 1 2
AABBC 2 2 1 2 1
AABCD 2 1 1 1 1 3
ABCDE 1 1 1 1 1 5
The green numbers are different. Instead of 6, 6*5, 6*5*4, ..., use
2, 2*1, 2*1*0, 2*1*0*-1, ... . Note that if the total of the blue
numbers is 3 or more, then the green number is 0:
red blue green
AAAAA 5 1 2
AAAAB 4 1 1 1 2
AAABB 3 2 1 1 2
AAABC 3 1 1 1 2 0
AABBC 2 2 1 2 1 0
AABCD 2 1 1 1 1 3 0
ABCDE 1 1 1 1 1 5 0
Now we calculate R and B, which are the same as for the 6-sided dice:
red blue green R B
AAAAA 5 1 2 120 1
AAAAB 4 1 1 1 2 24 1
AAABB 3 2 1 1 2 12 1
AAABC 3 1 1 1 2 0 6 2
AABBC 2 2 1 2 1 0 4 2
AABCD 2 1 1 1 1 3 0 2 6
ABCDE 1 1 1 1 1 5 0 1 120
The totals are N! * green / (R * B). N is 5.
red blue green R B total
AAAAA 5 1 2 120 1 2
AAAAB 4 1 1 1 2 24 1 10
AAABB 3 2 1 1 2 12 1 20
AAABC 3 1 1 1 2 0 6 2 0
AABBC 2 2 1 2 1 0 4 2 0
AABCD 2 1 1 1 1 3 0 2 6 0
ABCDE 1 1 1 1 1 5 0 1 120 0
The totals should add up to 2^5 = 32. They do, so the arithmetic
checks.
There are 2 ways of flipping all 5 coins the same. (HHHHH and TTTTT.)
There are 10 ways of flipping 4 coins the same and 1 different.
(HHHHT, HHHTH, HHTHH, HTHHH, THHHH, and
TTTTH, TTTHT, TTHTT, THTTT, HTTTT)
There are 20 ways of flipping 3 coins the same and 2 different.
(HHHTT, HHTHT, HHTTH, HTHHT, HTHTH, HTTHH, THHHT, THHTH, THTHH, TTHHH, and
TTTHH, TTHTH, TTHHT, THTTH, THTHT, THHTT, HTTTH, HTTHT, HTHTT, HHTTT)
ENUMERATING THE PATTERNS
How do you list all the patterns? You may find it intuitively
obvious, and then you just do it by the seat of your pants. If you
forget a pattern, the final check will fail.
But the rules for patterns are:
Write down some A's.
Write down some B's,
but there can't be more B's than A's.
Write down some C's,
but there can't be more C's than B's.
...
and keep doing that until you have enough letters. Do this in every
possible way.
Let's say we want to enumerate all the ways of throwing 6 dice.
If there are 6 A's, we're done. AAAAAA
If there are 5 A's,
then we need 1 B, and we're done. AAAAAB
If there are 4 A's, then
if there are 2 B's, were done. AAAABB
if there is 1 B, then there is 1 C, and we're done. AAAABC
If there are 3 A's, then
if there are 3 B's, were done. AAABBB
if there are 2 B's, then there is 1 C, and we're done. AAABBC
if there is 1 B , then there is 1 C and 1 D. AAABCD
(note that in this last case, having committed to
only one B, we can't have more than 1 C or D.)
If there are 2 A's, then
if there are 2 B's, then
if there are 2 C's, we're done. AABBCC
if there is 1 C, then there is 1 D, and we're done. AABBCD
if there is 1 B, then there is 1 C, 1 D, and 1 E. AABCDE
If there is 1 A, then there is 1 B, 1 C, 1 D, 1 E
and 1 F, and we're done. ABCDEF
And those are the patterns for 6 dice.
MATHEMATICS
Why does this work?
To calculate the number of ways of throwing a particular pattern, we
calculate two things. First, the number of ways of assigning die
values (1-6) to the letters in the pattern. Second, the number of
ways of assigning the letters to specific dice. The total number of
ways of throwing a pattern is the product of these two numbers.
The green number is the number of ways of assigning die values to
letters. But some of these assignments are equivalent. In the pattern
AAABBB, assigning 5 to A and 3 to B is the same as assigning 3 to A
and 5 to B because there really isn't any difference between A and B.
Dividing by B (the product of the b! for blue numbers 'b') throws away
the equivalent assignments, so that the number of different
assignments is (green / B).
There are N! ways of assigning letters to specific dice. But again,
some of these assignments are equivalent. For example, if there are
three A's, and we assign them to dice 2, 3, and 5, it doesn't matter
which A goes to which of the three dice because all the A's are the
same. Dividing by R (the product of the r! for red numbers 'r')
throws away the equivalent assignments here; the number of different
assignments is (N! / R).
The product of these two kinds of assignments, (green / B)*(N! / R),
is the total number of ways of throwing a particular pattern.