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.