07 November 2015

prerequisites: A basic knowledge of Haskell or similar.

1. Introduction

The goal of this blog post is to introduce Pascal’s triangle and the binomial coefficient.

The blog post is structured in the following way. In Section 2, we introduce Pascal’s triangle and formalize its construction. Before we define the binomial coefficient in Section 4, we first motivate its introduction by stating the Binomial Theorem in Section 3. The blog is concluded in Section 5.

2. Pascal’s triangle

Pascal’s triangle is a triangular array named after the French mathematician Blaise Pascal, despite the fact that mathematicians in India, Greece, and China had studied the triangle several centuries prior to Pascal1.

Traditionally, Pascal’s triangle is indexed over its rows and their individual entries. The row index is denoted and indexed from , referring to the top most row, while the entry index is denoted and also indexed from , referring to the leftmost entry of a given row. We define to be the th entry of the th row of Pascal’s triangle. Using a simple inductive approach we can construct Pascal’s triangle as follows:

  • Let row have a single entry, , with the value .
  • For each entry in the row , , calculate the value of the entry by adding the two entries just above it, i.e., the entries to its immediate left and right, , and if one of the two entries does not exist, then replace its value with .

In order to strengthen our intuition, the figure below shows the first five rows of Pascal’s triangle,

Here, we see that the entry , whose value is , is calculated by adding the entries and , both having the value , which again have been calculated by adding the values just above them, like so,

Now, in order to finish our formalization of Pascal’s triangle, we have to tweak the above inductive description a bit by making a few extra observations of the edge cases of Pascal’s triangle. As such, we notice that the two outer legs only consists of 1s,

which gives us two alternative base cases,

and,

However, these do not capture the entries for which , i.e., all values to the right of Pascal’s triangle,

but, as seen in the above figure, we can simply state that,

If we combine the three base cases listed above with the following adjusted version of the inductive case described at the beginning of this section,

which incidentally is called Pascal’s rule, we have obtained an elegant formalization of Pascal’s triangle capturing its main features.

Having defined Pascal’s triangle, we now take a small detour in order to state the Binomial Theorem, which we use to motivate the introduction of the binomial coefficient.

3. The binomial theorem

Given a binomial , where and are variables, and is a natural number, we want to describe the expansion of as a sum of its terms, each of which is called a monomial.

If we examine the first four expansions of , where , we get the following equations,

from which we notice a pattern that can be made more distinct by explicitly writing every coefficient and exponent of every monomial in the expansions,

Now it is clear that for a given binomial expansion the exponent of is decremented for each monomial of the expansion, starting at , as we traverse them from left to right. Conversely, the exponent of , starting at , is incremented for each monomial of the expansion. If we let denote the th monomial of an expansion, we can generalize the observation just made to the sum,

which generates the correct exponentiation of the monomials in the expansion. For example, if we let , we get,

which enumerates the monomials of the binomial expansion of , in Formula \ref{eq:binomial-expansions-example}, except for the coefficients of the monomials, which we still have to account for. Now, if we rearrange the monomials of Formula \ref{eq:binomial-expansions-example}, such that they are vertically aligned around the same center,

and remove everything but the coefficients,

we obtain the first four rows of Pascal’s triangle. Thus, the entries of Pascal’s triangle enumerate the coefficients of the monomials in the binomial expansion of . As such, we also refer to as the binomial coefficient, a concept we discuss further in the next section, since it gives us a way to calculate the coefficient of the th monomial in the binomial expansion of .

Returning to Formula \ref{eq:binomial-theorem-exponents}, we can now combine it with the binomial coefficient and obtain the sum,

which calculates the binomial expansion of the expression , yielding the following theorem.

Theorem 1 (Binomial theorem). Given two natural numbers and , and an exponent , the expression can be expanded into the sum,

where is the binomial coefficient. This expansion can also be written in summation notation as,

where the last equivalence follows from the symmetry of the sequence of binomial coefficients and of and .

Having stated the binomial theorem, we return to the binomial coefficient and show how to properly calculate and formalize it.

4. The binomial coefficient

As mentioned in the previous section, the binomial coefficient is equal to the coefficient of the th monomial in the binomial expansion of and can be read from Pascal’s triangle, as the th entry of the th row. This suggests that we can obtain a binomial coefficient function if we can reduce the formalization we came up with in Section 2 into something computable.

In order to come up with such a binomial coefficient function, we need to cover the base cases and the inductive cases for the row and column indices, n and k. Hence, we first observe that the base case , covers the two cases where (n = 0, k = 0) and (n > 0, k = 0), which leaves the cases (n = 0, k > 0) and (n > 0, k > 0). For the case (n = 0, k > 0), we know from the definition of Pascal’s triangle that for all values the result is , and similarly we know that the case (n > 0, k > 0) is the sum of the two entries just above it (n-1, k) and (n-1, k-1). Combining these observations we get the following Haskell definition,2

1
2
3
4
5
6
binomialCoefficient :: Int -> Int -> Int
binomialCoefficient n k
  | k == 0 = 1
  | n < k  = 0
  | n > 0 && k > 0 = binomialCoefficient (n - 1) k +
                     binomialCoefficient (n - 1) (k - 1)

where we express the rules above in terms of guards.

Having formalized the binomial coefficient and defined a function computing it, binomialCoefficient, we are ready to conclude this blog post.

5. Conclusion

In this blog post, we have introduced and formalized Pascal’s triangle and the binomial coefficient function.

We obtained the above results by first describing the construction of Pascal’s triangle in an inductive fashion, followed by formalizing Pascal’s triangle. Afterwards, we introduced the binomial coefficient function, as a result of describing the binomial theorem, and formalized it as the function binomialCoefficient, in Haskell.

In our next post, we look at what happens when we rotate Pascal’s triangle and the binomial coefficient, and their properties.

  1. See “Cambridge University Library: The great collection” (1998) by Peter Fox. 

  2. We quietly ignore the cases where n and k are negative, and instead treat them as natural numbers.