Rolling into Probability

There are 6 ways of rolling the sum of 7 with two dice. Is there a mathematical formula that will tell us this probability directly? This series attempts to discover one.

Introduction #

A YouTube video popped into my feed recently that presented a programmatic, recursive method to find how many ways there are of rolling a particular sum given a number of dice. For instance, it will return 6 ways for the parameters of 2 dice and 7 as a target sum. The essential idea is this:

const countDiceCombinations = (target, dice, memo = {}) => {
  if (memo[target + "," + dice]) {
    return memo[target + "," + dice]
  }

  if (dice === 0) {
    if (target === 0) {
      return 1
    } else {
      return 0
    }
  }

  let total = 0
  for (let i = 1; i <= 6; i++) {
    if (target >= i) {
      total += countDiceCombinations(target - i, dice - 1, memo)
    }
  }

  memo[target + "," + dice] = total
  return total
}

// Number of ways to get `10` with 3 dice:
console.log(countDiceCombinations(10, 3)) // should print 27

// Number of ways to get `7` with 2 dice:
console.log(countDiceCombinations(7, 2)) // should print 6

It's a recursive function that returns the solutions for dice-1 which in turn returns the solutions for dice-2 and so on. Clever!

But it got me thinking. Surely there could be a more direct way? Surely we can derive a mathemagical formula wherein we can just plug in the numbers directly without all that recursion? All that code? This post documents the first part of the journey towards a solution.

Naive, brutal #

It's worth revisiting what it is that we're doing.

The most straightforward way to know how likely an outcome is to brute force it: methodically go through all of the possibilities and count the target outcomes.

For instance, there are 36 ways of rolling two dice. They are listed here, with their sums in parenthesis.

(2) ⚀ ⚀
(3) ⚀ ⚁
(3) ⚁ ⚀
(4) ⚀ ⚂
(4) ⚁ ⚁
(4) ⚂ ⚀
(5) ⚀ ⚃
(5) ⚁ ⚂
(5) ⚂ ⚁
(5) ⚃ ⚀
(6) ⚀ ⚄
(6) ⚁ ⚃
(6) ⚂ ⚂
(6) ⚃ ⚁
(6) ⚄ ⚀
(7) ⚀ ⚅
(7) ⚁ ⚄
(7) ⚂ ⚃
(7) ⚃ ⚂
(7) ⚄ ⚁
(7) ⚅ ⚀
(8) ⚁ ⚅
(8) ⚂ ⚄
(8) ⚃ ⚃
(8) ⚄ ⚂
(8) ⚅ ⚁
(9) ⚂ ⚅
(9) ⚃ ⚄
(9) ⚄ ⚃
(9) ⚅ ⚂
(10) ⚃ ⚅
(10) ⚄ ⚄
(10) ⚅ ⚃
(11) ⚄ ⚅
(11) ⚅ ⚄
(12) ⚅ ⚅

As can be seen by counting items 16-21 in the list, there are 6 ways of rolling 7, out of the 36 ways the two dice can land. This simplifies to the statement that there is 1 chance in 6 of rolling a 7 when rolling two dice.

That 1 in 6 means something when evaluating risk. If you bet 1 money that a dice roll will turn up 7 and in exchange, will gain 5.99 money if you are right, you will lose all of your money in the long run. But if instead you gain 6.01 money, you can take that bet.

For another brute force example: in Dungeons and Dragons, the prototypical way to generate ability scores is to roll 3 six-sided dice. We can step through a similar process to find out that there is a 1 in 8 chance of rolling three six-sided dice in such a way that they will sum to 10 and a 1 in 8 chance of rolling an 11. Only 1 in 216 rolls would have the coveted 18, the highest natural score possible.

I won't list each outcome here because there are 216 of them, but if you're curious what that looks like, you can look at it on this gist. If you're keen, you can hand count the 54 ways of getting either 10 or 11.

Let's investigate less tedious ways to find these probabilities.

Pascal's Triangle #

Pascal's Triangle is a triangular array of numbers in which each number is the sum of the two numbers immediately above it. The triangle is named after the French mathematician Blaise Pascal.

            1

          1   1

        1   2   1

      1   3   3   1

    1   4   6   4   1

  1   5  10   10  5   1

1   6  15   20  15  6   1

This triangle has a long and ancient history stretching back to the 11th century in China. It is sometimes called the Khayyam-Pascal triangle in honor of the 11th century Persian mathematician Omar Khayyam, who also studied its properties.

One neat property of this triangle is that it can give the probability of getting a certain number of heads when flipping coins.

Listing out all possible outcomes of flipping one coin, there are only two:

⚫ (no heads)
🪙 (one head)

Let's ignore the top row of the triangle for now, other than to call it row 0. The next row we call row 1:

1  1

This row of the Triangle can represent the odds of getting 0 heads or 1 head when flipping one coin, sometimes expressed as a ratio 1:1. When flipping a coin, the "odds are even" that head will turn up or tail will turn up; each outcome is equally likely. Another way to put it is that the chances of getting 1 head is 1 in 2, or 1/2. To restate it, the first term indicates there is 1 in 2 chances of getting no heads and the second term indicates there is 1 in 2 chances of getting 1 head.

The next row, row 3 is:

1  2  1

1 : 2 : 1 can represent the odds of getting 0 heads, 1 head or 2 heads respectively when flipping two coins. This can be verbally expressed as "the odds of getting zero heads are one, the odds of getting one head are two, and the odds of getting two heads are one". Listing out all possible outcomes of two coin flips:

⚫⚫ (no heads)
⚫🪙 (one head)
🪙⚫ (one head)
🪙🪙 (two heads)

As can be seen, there is only 1 way in 4 of getting no heads, only 1 way in 4 of getting two heads, and 2 ways in 4 of getting one head, exactly as predicted by its corresponding row of the Triangle.

Erring on the side of over-explaining, let's walk through row 3 of Pascal's Triangle:

1  3  3  1

Listing all eight possible outcomes of flipping 3 coins:

⚫⚫⚫ (no heads)
⚫⚫🪙 (one head)
⚫🪙⚫ (one head)
🪙⚫⚫ (one head)
⚫🪙🪙 (two heads)
🪙⚫🪙 (two heads)
🪙🪙⚫ (two heads)
🪙🪙🪙 (three heads)

1 : 3 : 3 : 1 can be stated as "one chance in 8 of getting no heads, 3 chances in 8 of getting one head, 3 chances in 8 of getting two heads and 1 chance in 8 of getting three heads".

One interesting thing to note is that the sum of row n is 2ⁿ. That is to say, row 1 in the triangle sums to 2¹ or 2, and row 2 sums to 2² or 4, row 3 sums to 2³ or 8 and so on. And for completeness sake, the top row, row O sums to 2⁰ which is 1 and represents the sole possible outcome when flipping no coins!

This pattern of listing out probabilities holds forever. If you want to know the probabilty of getting exactly 2 heads when throwing 6 coins, you can list out the 6th row of Pascal's Triangle, count 3 terms from the right, pop it on top of its denominator 2⁶ and boom! You now have that probability: 15/64 or just shy of 1/4

But is there an easier way than listing out the entire Triangle?

Binomial expansion and binomial coefficients #

As a related aside, another neat property of the Triangle is that its rows can also represent coefficients of what's called a binomial expansion.

A binomial is an expression of two terms, like (a + b)ⁿ and to expand it is to multiply it out according to its power.

For an example of a binomial expansion, let's expand (a + b)²:

(a + b)² = (a + b)(a + b) = 1a² + 2ab + 1b²

Note that the coeffients of the expanded expression is 1 2 1, which is row 2 of Pascal's Triangle!

(By convention, coefficients of 1 are not usually noted. That is to say, the expression above is usually just a² + 2ab + b²)

And, it's exciting to say, the coefficients of the expansion of (a + b)³ are indeed 1 3 3 1:

(a + b)³ = 1a³ + 3a²b + 3ab² + 1b³

So, another way to get the probability of a specific number of heads in a specific number of coin flips is to raise a binomial to the power of the number of coins and expand it, then count over to the right coefficient.

So far, there are two ways of getting the probability of h heads in n coin flips

List out all of the possibilities for n coins and then count the specific outcomes with h heads.
Generate Pascal's Triangle down to row n then count over h terms starting with 0

Is there an even easier way?

Binomial coeffient formula #

What if there were some kind of formula by which we could go right to the correct term? How might one go about getting the term h of row n of the Triangle?

It turns out there is. One could use the "binomial coefficient formula":

C(n, h) = n! / (h! * (n - h)!)

(As a brief reminder in case you need it, x! is called n factorial and is equal to multiplying itself with all lower positive integers: x (x-1) (x-2)... 1)

Finding out the probability of throwing 2 heads when flipping 6 coins is a matter of plugging in the numbers:

C(6,2) = 6! / (2! * (6-2)!) = 720/36 = 15

And indeed, the third term (term 2) of row 6 of Pascal's Triangle is 15:

1 6 15 20 15 6 1

(Note that this is a zero-index formula, in that the first term in the row is 0 representing the outcome of 0 heads, just as the top row is the 0th row representing the case of flipping 0 coins)

Trinomial expansion and Pascal's triangle #

Let's modify Pascal's Triangle a bit. Instead of taking the sum of two terms above, let's take the sum of 3 terms:

            1

         1  1  1

      1  2  3  2  1

   1  3  6  7  6  3  1

1  4  10 16 19 16 10 4  1

Similar to the traditional Pascal's Triangle, this modified version depends on the row above it. Looking at the central term 3 in the third row, it's easy to see how it is the sum of the three 1s directly above it in the second row. Similarly, the 7 just below the 3 is the sum of the 3 and the two 2s to its left and right.

These rows represent the odds of getting a particular sum when rolling n 3-sided dice, with the top row 1 representing the result of rolling 0 dice: there is only one possible outcome! The second row, 1 1 1 represents the 3 equally likely outcomes when rolling a single 3-sided die: it's equally possible to get a 1, a 2 or a 3.

3-sided dice

The next row 1 2 3 2 1 represents, respectively, the probability of rolling 2, 3, 4, 5, and 6. To illustrate, listing out the 9 possible outcomes of throwing 2 three-sided dice:

(2) ⚀⚀
(3) ⚀⚁
(3) ⚁⚀
(4) ⚀⚂
(4) ⚁⚁
(4) ⚂⚀
(5) ⚁⚂
(5) ⚂⚁
(6) ⚂⚂

we see that there is only 1 possible way to get 2, 2 ways to get 3, 3 ways to get 4, 2 ways to get 5 and 1 way to get 6, as predicted by the third row (row 2) of the triangle.

Pretty neat! But, is there a nifty mathematical formula that lets us jump right to the term we want as there is in the case of coin-flipping? Something like

C₃(2,2) = 3

C₃(4,3) = 16

Given that Pascal's Triangle represent the coefficients in the expansion of a binomial is it possible that this modified Triangle represent the coefficents in the expansion of a trinomial? Like a binomial, a trinomial is an expression of a sum of variables raised to some power, but instead of two terms, it is three terms: (a + b + c)ⁿ.

Let's expand (a + b + c)² and see what the coefficients are. According to the Triangle, they should be 1 2 3 2 1 representing the probability of any particular sum of 2 three-sided dice:

(a + b + c)² = (a + b + c)(a + b + c)
              = a(a + b + c) + b(a + b + c) + c(a + b + c)
              = a² + ab + ac + ba + b² + bc + ca + cb + c²
              = a² + b² + c² + 2ab + 2ac + 2bc

This is just wrong. Wrong wrong wrong! Too many terms. What order should they be in? What even is 1 1 1 2 2 2?

But another kind of trinomial is x² + x + 1 and the coefficients of (x² + x + 1)² expanded out are:

(x² + x + 1)² = 1x⁴ + 2x³ + 3x² + 2x + 1

This is exactly right! Not only are the terms right, they are in the same order as the row in our triangle.

(This might imply that the binomial of the unmodified Pascal's Triangle is (x + 1) and not (a + b))

In any case, the modified trinomial version of Pascal's Triangle gives us the coefficients of (x² + x + 1)ⁿ.

Hexanomial expansion and Pascal's Triangle #

Since you brought up Dungeons and Dragons, let's modify Pascal's Triangle for 6-sided dice:

                                          1

                             1    1    1     1    1    1

                   1   2   3    4    5    6    5    4    3    2   1

         1   3   6  10  15   21   25   27   27   25   21   15  10   6   3    1

1  4  10  20  35  56  80  104  125  140  146  140  125  104  80  56  35   20   10  4  1

...

As before, each row is derived from the row above it, but here each term is the sum of the six terms above itself. As before, the probability of a particular sum of n six-sided dice is its term in the row over the denominator 6ⁿ.

For example, to calculate the probability of getting a 10 when rolling 3 six-sided dice, find row 3 (remembering that row 0 is the top row):

row 3:  1   3   6  10  15   21   25   27   27   25   21   15  10   6   3    1

These terms represent, respectively, the odds of getting a sum of 3, 4, 5, 6, 7 and so on up to 18. The probability of getting a 10 therefore, is 27 over 216 or 1/16. The probability is the same for 11, so the probability of getting either 10 or 11 is 1 in 8.

Multinomial expansion and the multinomial coefficient formula #

We had binomials and trinomials and hexanomials. Let's generalize.

Multinomials are expressions like (a + b + c ... + k)ⁿ, and there is indeed a multinomial coefficient formula that will tell us the coefficients of the terms in that expansion. Since this is related to what we're trying to do, let's take a look:

C(n; a, b, c, ..., k) = n! / (a!b!c! ... k!)

where a + b + c + ... + k = n

Purportedly, plugging numbers into that formula will give us coefficients of that expansion.

For instance, given that (a + b + c)³ expands out to:

a³ + b³ + c³ + 3a²b + 3a²c + 3ab² + 3ac² + 3b²c + 3bc² + 6abc

any purported multinomial coefficient formula that represents this trinomial expansion should only ever return either 1 or 3 or 6, since those are the only coefficients in that expanded expression.

Taking a pause here for a moment, let's see how the formula wants us to represent each term.

a³ would be represented as 3,0,0 because a has 3 for an exponent and both b and c have no exponent
a²b would be 2,1,0 because a has 2 for an exponent, b has 1 and c has no exponent
abc would be 1,1,1 because each of a, b and c have 1 for an exponent

And a + b + c should always and only sum to 3. No 3,2,1, for instance.

If it works, the formula will tell us if the term abc has a 6 or 3 or whatever in front of it.

Applying the multinomial coefficient formula to each term in turn:

Distribution (3, 0, 0): a³
Multinomial coefficient = (3!)/(3!0!0!) = 1
Term = 1 * a³ = a³

Distribution (0, 3, 0): b³
Multinomial coefficient = (3!)/(0!3!0!) = 1
Term = 1 * b³ = b³

Distribution (0, 0, 3): c³
Multinomial coefficient = (3!)/(0!0!3!) = 1
Term = 1 * c³ = c³

Distribution (2, 1, 0): a²b
Multinomial coefficient = (3!)/(2!1!0!) = 3
Term = 3 * a²b = 3a²b

Distribution (2, 0, 1): a²c
Multinomial coefficient = (3!)/(2!0!1!) = 3
Term = 3 * a²c = 3a²c

Distribution (1, 2, 0): ab²
Multinomial coefficient = (3!)/(1!2!0!) = 3
Term = 3 * ab² = 3ab²

Distribution (1, 0, 2): ac²
Multinomial coefficient = (3!)/(1!0!2!) = 3
Term = 3 * ac² = 3ac²

Distribution (0, 2, 1): b²c
Multinomial coefficient = (3!)/(0!2!1!) = 3
Term = 3 * b²c = 3b²c

Distribution (0, 1, 2): bc²
Multinomial coefficient = (3!)/(0!1!2!) = 3
Term = 3 * bc² = 3bc²

Distribution (1, 1, 1): abc
Multinomial coefficient = (3!)/(1!1!1!) = 6
Term = 6 * abc = 6abc

What we have is:

1  3  3  6  3  3  1
      3  1  3

and what we're looking for is:

1  3  6  7  6  3  1

Hmm. Interesting. If we combine (add) some of the terms, we get what we're looking for. But which terms can be added, which must stay separate?

1a³  3a²c  3c²a   1c³    3c²b  3b²c   1b³
           3a²b  6abc    3b²a
1    3     6      7      6     3      1

Abrupt cliffhanger #

With this description of the problem and gesturing vaguely at a solution, I am putting aside my laptop, getting up and going outside to enjoy this marvelous day. Perhaps the answer will present itself to my subconscious? Your comments are, as always, welcome!