Pascal’s Triangle

There is only one way to choose nothing.

If there is no thing to choose, you have a choice: choose nothing.

If there are two things from which to choose, choosing nothing is still a choice.

Austin, TX

I used to tell my students a story about counting goats as the birth of mathematics. They knew I was kidding, but this notion may not be far from the mark. About 30,000 years ago, Paleolithic people scratched markings into bone to represent numbers. (Check out the chronology in the MacTutor History of Mathematics archive.)

While this bone-scratching predates domestication of livestock, food seems like a possible motivator for counting. Maybe fantastical, but I imagine a precocious goatherd discovering counting to keep track of the goats in his flock. With the advent of trade, counting would have become all the more interesting for the goatherd.

Let’s say your neighbor has one goat and offers to sell it to you. You may choose to buy the goat or not. Each option has one manifestation. That is, there is one way to not buy the goat and one way to buy the goat. (This may seem confusing. Sometimes the trivial cases are.)

If your neighbor has two goats, a brown one and a white one, and offers to sell them to you, what purchasing options do you have?

(0) You could choose to not buy a goat. There is one way to do that.

(1) If you choose to buy only one goat, there are two ways to do so: buy the white one or the brown one.

(2) There is only one way to buy both goats: buy both goats.

Imagine your neighbor has three goats. Hopefully, you can sort out the number of options if you choose to buy 0 or 1 goat. What if you decide to buy 2 goats? How many distinct goat pairs could you make?

Listing is an easy way to answer this question, especially if you name the goats. Let’s use goat1, goat2, and goat3 as their names. (Creative, I know.) Here are the possible pairs:

{goat1, goat2}
{goat1, goat3}
{goat2, goat3}

That is it; there are only three distinct pairs. It might be tempting to include something like {goat3, goat2}, but we already have that pair as {goat2, goat3}. We are simply making combinations, where the order does not matter.

That last 1 is the number of ways to buy all three goats. “Would you like to buy these three goats?” asks your neighbor. You say, “Yes.”

We have now completed the first four lines of Pascal’s Triangle.

In 1665, several years after his game-changing correspondence with Pierre de Fermat, Pascal’s Traité du triangle arithmétique (Treatise on the Arithmetical Triangle) was published. Pascal’s Triangle was included in this treatise, but it was known well before Pascal. For example, in 1261 Yang Hui included the first six lines of the triangle in his Xiangjie jiuzhang suanfa (Detailed analysis… ). Still, Pascal’s treatise organized a body of knowledge connected to counting, establishing forms and language we recognize today (after translation, at least).

Pascal’s Triangle provides a shortcut for answering counting questions, such as the ones posed above. For another example, let’s say you wanted to know how many distinct 3-person teams are possible if you are choosing from 5 people.

Go to the line with 1 5 …

This is the line to use when choosing from 5 objects. In math discussions, we use “choose” as an operational word. Saying “5 choose 3” is another way of asking “How many distinct combinations of 3 objects can be made when choosing from a set of 5 objects?” From the line of Pascal’s Triangle, we can see 5 choose 0 is 1, 5 choose 1 is 5, and so on. To answer the current question, we want the result of 5 choose 3.

If we wanted to know how many distinct pairs we could make from 1000 goats, Pascal’s Triangle is not the ideal tool. We would need to expand the triangle to include 1001 lines. That seems laborious. It is possible to arrive at an answer, without using the triangle.

If you choose one goat, call him William, then you have 999 other goats you could pair with William. Choose another goat, call him Tumnus, and you have an additional 998 possible pairings. (We already counted the {William, Tumnus} pair once. We don’t want to double count.)

We could proceed this way, eventually adding 999 + 998 + … + 1 to discover how many unique pairs. This sort of brute force may seem acceptable for counting pairs, but what if I asked how many triplets could be formed? The complexity increases dramatically when forming triplets. As you may know or have guessed by now, there are other routes to arrive at an answer—quicker methods that unlock this and even more challenging questions.

Combinatorics is a branch of mathematics whose fruit includes methods for answering tough counting questions. This business of choosing and the related calculation methods are included in combinatorics. Before getting to a formula for 5 choose 3 or even 1000 choose 2, it will be helpful to answer some other counting questions.