Pascal's Arithmetical Triangle

In 1653, Blaise Pascal, concerned with questions that would lay the foundation of probability theory, collected several facts about a triangular array of numbers in his Treatise on Arithmetical Triangle. This arrangement of numbers appeared as early as the 10th century in China, India, and Persia. The Chinese and Persian treatment of the triangle was in service of what we would now consider algebra: finding \(n\)th roots, essentially solving polynomial equations. The numbers in the triangle appear as solutions to counting problems in Indian texts: from six tastes, how many combinations of one, or two, or three,... can you make? European mathematicians in the 14th century presented the triangle as a table of figurate numbers (numbers that can be arranged in a geometric shape), which were themselves the centerpiece of the work of Pythagoras and his followers.

So what is this remarkable triangle that holds the secrets of so many different mathematical problems? Behold, Pascal's triangle:

Spend some time gazing at the beauty of this triangle. What do you notice? What do you wonder? Look specifically at the 5th row (we call the 1 on the top row 0, so row 5 is 1, 5, 10, 10, 5, 1). How do the numbers in this row relate to the numbers above them? Notice that \(5 = 1+4\) and \(10 = 4+6\). Does this occur anywhere else in the triangle?

Indeed, every number in the triangle is the sum of the two numbers above it. Let's take this as our definition of Pascal's triangle. We can then generate as many rows of the triangle as we like. It is this additive definition that was used in China and Persia to find \(n\)th roots, and we will briefly mention this use at the end of this section. However, we are interested in counting questions, so our main goal now is to observe how the numbers of Pascal's triangle are answers to a variety of counting questions.

Here are some apparently different discrete objects we can count: lattice paths, bit strings, subsets, and pizzas. We will give an example of each type of counting problem (and say what these things even are). As we will see, the numbers in Pascal's triangle are the answers to all of these questions.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

The integer lattice is the set of all points in the Cartesian plane for which both the \(x\) and \(y\) coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines.

A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the point \((0,0)\) to \((3,2)\):

Notice that to ensure the path is the shortest possible, each move must be either to the right or up. Additionally, in this case, no matter what path we take, we must make three steps right and two steps up. No matter in what order we make these steps, there will always be five steps. Thus each path has length five.

The counting question we will ask is this: how many lattice paths are there between \((0,0)\) and \((3,2)\)? In this case, drawing all the paths wouldn't take too long. Or we could list each path as a string of directions such as \(xxyyx\), \(yyxxx\), or \(xyxxy\), which correspond to the three paths drawn above, where an \(x\) means travel one unit in the \(x\) direction, and similarly for \(y\). We would get the following ten paths: \[\begin{aligned}xxxyy \qquad xxyxy \qquad xyxxy \qquad yxxxy \\ xxyyx \qquad xyxyx \qquad yxxyx \qquad xyyxx \qquad yxyxx \qquad yyxxx\end{aligned}\]. When the distance between starting and stopping points is larger, we will want to find a more efficient way to count the paths.

Let's take what we learned from the rook paths (which are, gasp, actually lattice paths). Consider the lattice shown below:

Any lattice path from (0,0) to (3,2) must pass through exactly one of \(A\) and \(B\). The point \(A\) is 4 steps away from (0,0) and two of them are in the \(x\) direction. The last step is also in the \(x\) direction, so the paths from (0,0) to (3,2) that pass through \(A\) are exactly the six strings we listed above that end in an \(x\). For the paths that pass through point \(B\), the last step will be in the \(y\) direction, so the paths from (0,0) to (3,2) that pass through \(B\) are exactly the four strings we listed above that end in a \(y\). So the total number of paths to (3,2) is just \(6+4\).

To make this observation helpful for actually finding the number of paths from the origin to a given point, we note that it is the length of the path that determines the row of Pascal's triangle, and the number of steps in the \(y\) direction that says how far into the triangle we are -- the column of Pascal's triangle.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Bit is short for binary digit, so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings: \[1001 \quad 0 \quad 1111 \quad 1010101010\].

The number of bits (0's or 1's) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1's. The number of 1's in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.

For example, the elements of the set \(\B^3_2\) are the bit strings 011, 101, and 110. Those are the only strings containing three bits, exactly two of which are 1's.

The counting questions: How many 5-bit strings have weight 3? In other words, we are asking for the cardinality \(|\B^5_3|\).

Let's just list them and see how many there are. \[\begin{aligned}11100 \qquad 11010 \qquad 10110 \qquad 01110 \\ 11001 \qquad 10101 \qquad 01101 \qquad 10011 \qquad 01011 \qquad 00111\end{aligned}\]. Great. Ten of them. Actually, I have a confession: I didn't type all of these from scratch. Instead I just modified the list of 10 lattice paths from (0,0) to (3,2) that we found earlier. Each \(x\) became a 1 and each \(y\) became a 0. After all, any lattice path with length \(n\) that requires \(k\) steps in the \(x\) direction can be represented by a string of \(n\) symbols of two types, with \(k\) of those symbols being of one type. Whether we call the two symbols \(x\) and \(y\) or we call them \(1\) and \(0\) will not change how many strings we get.

Now we have two good reasons to believe that Pascal's triangle tells us the number of bit strings of a given weight: There is a one-to-one correspondence between lattice paths and bit strings, and the same recursive relationship holds for bit strings as it does for generating Pascal's triangle. So we can now use the triangle to count bit strings.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

A subset of a set \(A\) is any set all of whose elements are also in \(A\). Think of starting with the set \(A\) and removing some (or none or all) of its elements: the resulting set is a subset of \(A\). (More information about sets can be found in and .)

Suppose we look at the set \(A = \{1,2,3,4,5\}\). How many subsets of \(A\) contain exactly 3 elements? Let's list them all: \[\begin{aligned}\{1,2,3\} \qquad \{1,2,4\} \qquad \{1,3,4\} \qquad \{2,3,4\} \\ \{1,2,5\} \qquad \{1,3,5\} \qquad \{2,3,5\} \qquad \{1,4,5\} \qquad \{2,4,5\} \qquad \{3,4,5\}\end{aligned}\].

Again, we see there are ten. In fact, we have listed them in the same order as we listed the ten 5-bit strings of weight 3 and the ten lattice paths from (0,0) to (3,2). Wait, does this even make sense? In what way is a subset the same as a bit-string?

Think of each bit in a bit string as representing one of the elements in a set. The set \(A\) has five elements, so we need five bits to represent a subset of \(A\). If the bit in position \(n\) is a 0, that means we do not include \(n\) in our subset, while a 1 in that position tells us that \(n\) is in the subset. Three 1's means we have said, yes to three elements.

This example illustrates that, once again, Pascal's triangle can give us the answer to a counting question. The number of \(k\)-element subsets of a set with \(n\) elements is the same as the number of \(n\)-bit strings of weight \(k\), and that is the number in row \(n\), column \(k\) of the triangle: \(\binom{n}{k}\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Earlier we said that one of the original uses for Pascal's triangle was to solve problems in algebra. What does counting subsets (or bit strings or lattice paths) have to do with algebra?

Suppose you expand the binomial expression \((x+1)^6\) (i.e., multiply the binomial \(x+1\) by itself six times). This can be tedious to do by hand, but a computer algebra system such as SageMath can do this easily.

Do the coefficients look familiar? Consider the 6th row of Pascal's triangle: \[1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1\]. Why are these the coefficients?

To see why this is more than just a coincidence, let's look at the expansion of \((x+y)^3\) and do it very carefully. We are really multiplying out \[(x+y)(x+y)(x+y)\]. This means we must distribute the binomials, which looks like the following. (We will use a different typeface for each version of the \(x\) and \(y\) to keep track of where everything comes from.) \[\begin{aligned}(x+y)^3 = \amp (x+y)(\x+\y)(\X+\Y) \\ = \amp [(x+y)(\x+\y)]\X + [(x+y)(\x+\y)]\Y \\ = \amp [(x+y)\x + (x+y)\y]\X + [(x+y)\x+ (x+y)\y] \Y \\ = \amp [x\x + y\x + x\y + y\y]\X + [x\x + y\x + x\y + y\y]\Y \\ = \amp x\x\X + y\x\X + x\y\X + y\y\X + x\x\Y + y\x\Y + x\y\Y + y\y\Y\end{aligned}\]. This repeated distribution results in a sum of terms, each the product of three variables. We see that each term is the result of choosing either the \(x\) or the \(y\) from each of the binomials. For example, the term \(x\y\X\) is the result of choosing the \(x\) from the first binomial, the \(\y\) from the second, and the \(\X\) from the third.

Say we want to find the coefficient of the \(x^2y\) term. We collect like terms, collecting all the terms in which we have chosen \(x\) two times (and \(y\) the other one time). Alternatively, the \(x^2y\) term comes from all the strings with two \(x\) and one \(y\), just like a bit string or lattice path. No matter how you think of it, the result is that we have \(\binom{3}{2} = 3\) terms with the form \(x^2y\).

Hopefully it is clear that this generalizes to the expansion of \((x+y)^n\) for any positive integer \(n\). This is known as the binomial theorem.

For this reason, the numbers in Pascal's triangle are often called binomial coefficients.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.