## Dice, Triangles and Trinomials

math

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.

1. (2) ⚀ ⚀
2. (3) ⚀ ⚁
3. (3) ⚁ ⚀
4. (4) ⚀ ⚂
5. (4) ⚁ ⚁
6. (4) ⚂ ⚀
7. (5) ⚀ ⚃
8. (5) ⚁ ⚂
9. (5) ⚂ ⚁
10. (5) ⚃ ⚀
11. (6) ⚀ ⚄
12. (6) ⚁ ⚃
13. (6) ⚂ ⚂
14. (6) ⚃ ⚁
15. (6) ⚄ ⚀
16. (7) ⚀ ⚅
17. (7) ⚁ ⚄
18. (7) ⚂ ⚃
19. (7) ⚃ ⚂
20. (7) ⚄ ⚁
21. (7) ⚅ ⚀
22. (8) ⚁ ⚅
23. (8) ⚂ ⚄
24. (8) ⚃ ⚃
25. (8) ⚄ ⚂
26. (8) ⚅ ⚁
27. (9) ⚂ ⚅
28. (9) ⚃ ⚄
29. (9) ⚄ ⚃
30. (9) ⚅ ⚂
31. (10) ⚃ ⚅
32. (10) ⚄ ⚄
33. (10) ⚅ ⚃
34. (11) ⚄ ⚅
35. (11) ⚅ ⚄
36. (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   11   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:

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:

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:

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

1. List out all of the possibilities for `n` coins and then count the specific outcomes with `h` heads.
2. 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  11  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 `1`s directly above it in the second row. Similarly, the `7` just below the `3` is the sum of the `3` and the two `2`s 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`. 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``

or

``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    11  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²a1    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!