Pascal’s Triangle and Dice Rolls

Pascal’s Triangle

Pascal’s Triangle represents the coefficients of a binomial such as \(x + 1\) raised to a power. Row n of the triangle lists the coefficients of \((x + 1)^{n-1}\). Here are the first few rows of Pascal’s Triangle: \[\newcommand\cn[3]{\llap{#1}#2\rlap{#3}} \begin{array}{c} &&&&&&\cn{}{1}{}\\ &&&&&\cn{}{1}{}&&\cn{}{1}{}\\ &&&&\cn{}{1}{}&&\cn{}{2}{}&&\cn{}{1}{}\\ &&&\cn{}{1}{}&&\cn{}{3}{}&&\cn{}{3}{}&&\cn{}{1}{}\\ &&\cn{}{1}{}&&\cn{}{4}{}&&\cn{}{6}{}&&\cn{}{4}{}&&\cn{}{1}{}\\ &\cn{}{1}{}&&\cn{}{5}{}&&\cn{1}{}{0}&&\cn{1}{}{0}&&\cn{}{5}{}&&\cn{}{1}{}\\ \cn{}{1}{}&&\cn{}{6}{}&&\cn{1}{}{5}&&\cn{2}{}{0}&&\cn{1}{}{5}&&\cn{}{6}{}&&\cn{}‌​{1}{} \end{array}\]

For instance, row 4 is (1, 3, 3, 1). This means that \[(x+1)^3 = x^3 + 3x^2+ 3x + 1\] (which it does). Row 6 is (1, 5, 10, 10, 5, 1), and \[(x+y)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x +1\]

There are three ways of generating a given row in Pascal’s Triangle. The first is to expand \((x+1)^{n-1}\). The second is iterative: Each value is equal to the sum of the two values immediately above it. For instance, take Row 5: (1, 4, 6, 4, 1). The sums of each pair of numbers, going from left to right, are (5, 10, 10, 5). Note these are the middle numbers in Row 6. The third way to generate Pascal’s Triangle is also iterative, but more complex; I’ll discuss it below.

Flipping a Coin and Rolling a Die

Let’s take a standard coin. If we flip a coin five times, how many different ways could we get three heads and two tails?

Pascal’s Triangle tells us. Row 6 is (1, 5, 10, 10, 5, 1). That means there is one way to get five heads, five ways to get four heads and a tail (HHHHT, HHHTH, HHTHH, HTHHH, THHHH), ten ways to get three heads and two tails, and so on. Adding up the values for row 6 gives us 32; there are 10 ways to get three heads and two tails, and a probability of \(\frac{10}{32} = \frac{5}{16} = 31.25\%\) of doing so.

What about rolling a die? Let’s say we have a standard 6-sided die and roll it three times. What are the possible sums? The lowest (rolling all 1s) is three; the highest (rolling all 6s) is eighteen. But what is the distribution?

If we roll the die just once, the distribution of possible sums is (1, 1, 1, 1, 1, 1), with a range from one to six. If we roll it twice, the distribution is (1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1), with a range from two to twelve; for instance, there are three ways to get a sum of 4 ((1, 3), (2, 2), (3, 1)), and four ways to get a sum of 5 ((1, 4), (2, 3), (3, 2), (4, 1)). If we roll it three times, the distribution is (1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1), with a range from three to eighteen. So if we wanted to know what the likelihood of rolling a total of six on three dice, we could figure it out: There are 10 ways to do so, and a total of 216 (or \(6^3\)) ways to roll three dice, for a likelihood of \(\frac{10}{216} = \frac{5}{108} \approx 4.63\%\).

The question is: Is there a way to generate these numbers? And is there a general pattern?

It turns out, just as Pascal’s Triangle serves double duty for coin tosses and binomial coefficients, the distribution of sums of dice rolls matches the coefficients for \((x^5 + x^4 + x^3 + x^2 + x + 1)^n\). This is called the sextinomial coefficient array. Hence, a particular row could be generated by expanding \((x^5 + x^4 + x^3 + x^2 + x + 1)^n\) and collecting the coefficients.

There is also an iterative process, albeit not as straightforward as the one for Pascal’s Triangle. It is easier to explain using a left-adjusted triangle instead of a centered one. Here are the first four rows: \[\begin{matrix} 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 \end{matrix}\]

For the first six elements on each row, the pattern is straightforward: Add the number immediately above and the number to the left (use 0 if the number does not exist). However, after the sixth element, that pattern breaks down.

As Vrublevsky points out, the remaining values on each row result from subtracting the element one up and six to the left. For instance, on Row 4, element 7 is \(5 + 21 – 1 = 25\), while element 8 is \(4 + 25 – 2 = 27\). Adjusting the notation there gives us: \[a_{nj} = a_{n(j-1)} + a_{(n-1)j} – a_{(n-1)(j-6)}\] where \(n\) represents the row number and \(j\) represents the column within that row.

We can generalize this equation for all values in the array except Row 1 if we assume that an undefined element is equal to 0. Then if \(a_{11} = 1\) and the rest of Row 1 is blank, the rest of the grid will follow.

To see this, let’s look at Row 2: \[a_{21} = a_{20} + a_{11} – a_{1^-5} = 0 + 1 – 0 = 1\\ a_{22} = a_{21} + a_{12} – a_{1^-4} = 1 + 0 – 0 = 1\\a_{23} = a_{22} + a_{13} – a_{1^-3} = 1 + 0 – 0 = 1\\a_{24} = a_{23} + a_{14} – a_{1^-2} = 1 + 0 – 0 = 1\\a_{25} = a_{24} + a_{15} – a_{1^-1} = 1 + 0 – 0 = 1\\a_{26} = a_{25} + a_{16} – a_{10} = 1 + 0 – 0 = 1\\a_{27} = a_{26} + a_{17} – a_{11} = 1 + 0 – 1 = 0\]

We leave \(a_{17}\) off the row, and continue to Row 3, the first nine values being: \[a_{31} = a_{30} + a_{21} – a_{2^-5} = 0 + 1 – 0 = 1\\ a_{32} = a_{31} + a_{22} – a_{2^-4} = 1 + 1 – 0 = 2\\a_{33} = a_{32} + a_{23} – a_{2^-3} = 2 + 1 – 0 = 3\\a_{34} = a_{33} + a_{24} – a_{2^-2} = 3 + 1 – 0 = 4\\a_{35} = a_{34} + a_{25} – a_{2^-1} = 4 + 1 – 0 = 5\\a_{36} = a_{35} + a_{26} – a_{20} = 5 + 1 – 0 = 6\\a_{37} = a_{36} + a_{27} – a_{21} = 6 + 0 – 1 = 5\\a_{38} = a_{37} + a_{28} – a_{22} = 5 + 0 – 1 = 4\\a_{39} = a_{38} + a_{29} – a_{23} = 4 + 0 – 1 = 3\]

Row 4 is less trivial, the first nine values being: \[a_{41} = a_{40} + a_{31} – a_{3^-5} = 0 + 1 – 0 = 1\\ a_{42} = a_{41} + a_{32} – a_{3^-4} = 1 + 2 – 0 = 3\\a_{43} = a_{42} + a_{33} – a_{3^-3} = 3 + 3 – 0 = 6\\a_{44} = a_{43} + a_{34} – a_{3^-2} = 6 + 4 – 0 = 10\\a_{45} = a_{44} + a_{35} – a_{3^-1} = 10 + 5 – 0 = 15\\a_{46} = a_{45} + a_{36} – a_{30} = 15 + 6 – 0 = 21\\a_{47} = a_{46} + a_{37} – a_{31} = 21 + 5 – 1 = 25\\a_{48} = a_{47} + a_{38} – a_{32} = 25 + 4 – 2 = 27\\a_{49} = a_{48} + a_{39} – a_{33} = 27 + 3 – 3 = 27\]

We can continue in this fashion.

Generalizing the Pattern

If we rewrite the Pascal’s Triangle to be left-aligned instead of center-aligned, we can apply the same formula: \[\begin{matrix} 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 \end{matrix}\]

Row 1 is always the same: \(a_{11} = 1\) and blank otherwise. Each element in row 2 and below is calculated using \[a_{nj} = a_{n(j-1)} + a_{(n-1)j} – a_{(n-1)(j-2)}\] That is, add the element above to the element to the left (if both exist), then subtract the element up one and to the left two (if it exists). Row 6 can be easily verified: \[a_{61} = a_{60} + a_{51} – a_{5^-1} = 0 + 1 – 0 = 1\\ a_{62} = a_{61} + a_{52} – a_{50} = 1 + 5 – 0 = 6\\a_{63} = a_{62} + a_{53} – a_{51} = 6 + 10 – 1 = 15\\a_{64} = a_{63} + a_{54} – a_{52} = 15 + 10 – 5 = 20\\a_{65} = a_{64} + a_{55} – a_{53} = 20 + 5 – 10 = 15\\a_{66} = a_{65} + a_{56} – a_{54} = 15 + 1 – 10 = 6\\a_{67} = a_{66} + a_{57} – a_{55} = 6 + 0 – 5 = 1\\a_{68} = a_{67} + a_{58} – a_{56} = 1 + 0 – 1 = 0\]

And what of different sizes of dice? There are two ways to determine the distribution of values for n rolls of an m-sided die. The first is to expand the polynomial \((x^m + x^{m-1} + … + 1)^{n-1}\). The second is to generate the array based on seeding Row 1 with \(a_{11}=1\) and then applying \[a_{nj} = a_{n(j-1)} + a_{(n-1)j} – a_{(n-1)(j-m)}\] to Row 2 and below.

Keep in mind that the first element of each row is the number of ways to get that row’s number as a sum (rather than 1 as a sum), and so on to the right.

This pattern can be verified using the established arrays for binomials, trinomials, quadrinomials, quintonomials, sextinomials, septinomials, octonomials, 9-nomials, and 10-nomials.

Note that Pascal’s Triangle results from an iterative process that generates the rest of the polynomial coefficients, but this iterative process is not the standard iteration (which is simpler).