Pascal’s Triangle: how I love how thee let me count the ways

The Staircase of Mount Meru. Khayyam’s Triangle. Yang Hui’s Triangle. There are many names for Pascal’s Triangle.

I was shown this triangle in school and told we could use it to get combinations and binomial coefficients. I don’t remember being excited at the time. But that’s because I didn’t know why we could do that. I’ll explain how the numbers in Pascal’s triangle correspond to those things as well as why the rows correspond to the powers of eleven.

Quick refresher on combinations (and permutations)

Combinations: if there are 5 different ice-cream flavours, how many ways can I combine 3 different flavours? This problem is called “n choose k”, in this example “5 choose 3”. It is written as

Permutations: if there are 5 different ice-cream flavours, how many ways can I arrange 3 different flavours in a stack on the cone? Permutations are ordered. Permutations are ordered lists; combinations are sets.

If we have flavours Apricot, Banana, Chocolate, Durian and Elderberry, ABCDE, for short, then the number of permutations is the number of strings with three elements:

Which is 5 x 4 x 3: for the first position we have 5 choices, then for the next position we have 4 choices, then for the next position we have 3 choices. We can create a formula for this using factorial

The (n-k)! part is there to get rid of the extra multiplications because we only wanted to use 3 out of 5 flavours for our ice cream stack. If we wanted permutations of the entire set of elements, the formula would just be n! . Plugging in for our example, the number of permutations of 3 elements from 5 is

To calculate the number of combinations, we can take all the permutations and “collapse” the ones that are duplicates of the same combination. For example, ABC, ACB, BAC, BCA, CAB and CBA are permutations of the same combination. The exact number of duplicates is the number of permutations for each combination. So the formula for combinations is

which when using the terminology (n choose k)

So the number of combinations of 3 flavours from 5, or (5 choose 3) is

Now we have precise formulas to know how many different ice cream creations we can make both taking order into account (permutations), and not into account (combinations). Neat!

So far this has nothing to do with Yang Hui’s triangle. So let’s get to that. We were told that the numbers in Yang Hui’s triangle correspond to (n choose k) combination numbers like so

So if we want to know (5 choose 3) we read it off the row in the triangle, and indeed the number at position (5 3) is 10. But why does this work out? As a student I never thought to ask why. We were generally discouraged from doing so. But the answer is pretty simple and cool. The numbers in Yang Hui’s triangle are generated by a recursive rule. And so are the number of combinations.

Each number in the triangle (except the ones) is made by adding the two numbers diagonally above it. Combinations are defined by the same recursive rule.

You can see how n combinations are built from n-1 combinations. Take our example of (5 choose 3) — the number of combinations of 3 letters from the set ABCDE. First we could get all the combinations of 2 letters from BCDE and stick an A on it–that gives us all 3 letter combinations with A. Secondly we can get all combinations of 3 letters from BCDE, and that should give us all possible combinations of 3 letters.

The first group is (n-1 choose k-1) and the second group is (n-1 choose k). If we look again at the triangle, indeed we see that (5 choose 3) is made by adding (4 choose 2) and (4 choose 3).

The numbers in the triangle correspond to the number of combinations because they are generated with the same recursive rule. Pretty interesting that there is both a recursive definition and an algebraic formula for combinations. Is there always a formula for a recursive definition? Maybe there exists then an algebraic formula for the Fibonacci sequence? Is there a systematic way to get an algebraic formula from a recursive definition? So far coming up with these algebraic formulas seems to require creativity.

The other thing we were told about Yang Hui’s triangle is that the numbers are binomial coefficients. The rows of the triangle help us expand expressions like

For example

As a child I had never needed to expand one of these kind of expressions so I wasn’t very excited. As an adult I have still never needed to expand one of these expressions, but now I am fond of asking why: why do the triangle rows work out to be the coefficients of these expanded expressions? What does it have to do with combinations?

Turns out, expanding these expressions is a combinatoric problem.

To perform the multiplication, for each bracket you choose either an x or a y to combine with the others to produce a term.

These terms are permutations. We combine the terms to get the final expansion

The question of how many x³y² terms there are, ie. how many terms with 3 x’s and 2 y’s, is an (n choose k) problem: (5 choose 3). We can think of it as if the x’s have a subscript for which bracket they came from

Then we have 5 unique symbols, x₁ to x₅, and the number of combinations of three of those symbols is the coefficient for the term x³y². Another way of thinking about it: for the strings we generate

we can give each position in the string a number from 1 to 5. The number of terms with 3 x’s in them is number of ways they can occupy three positions in the string: {1,2,3}, {1,2,4}, {1,2,5} etc.

What are binomials anyway? Who cares about expanding them? Please let me know. One guess is that people just liked analysing numbers. In geometry they were obsessed with squaring and cubing things, and since all numbers can be expressed as the sum of two other numbers, it’s kinda interesting to know what happens to the parts that make up the sum for higher powers. Kinda. At least that is what the Persian mathematician Al-Karaji, who discovered the binomial theory in the 10th century, seemed to be into.

Funnily enough, it was as I was staring at the binomial expression that I realised why the rows of Yang Hui’s triangle correspond to the powers of 11¹.

From the 5th power onward the numbers don’t match up perfectly, but if you read the digits as powers of 10 and then carry them through, they still do. For example 1×10⁵ + 5×10⁴ + 10×10³ + 10×10² + 5×10¹ + 1×10⁰ = 161051 = 1¹⁵.

Why? Isn’t that a freaky coincidence? Not if we consider that 11 = (1 + 10) and if, for every successive power of n we expand the expression

because one of the numbers is 1, we get a sequence of powers of 10 with the binomial coefficient…that represent the nth power of 11 in decimal…

Just one more magic pattern before I move onto the next blog post. Yang Hui’s triangle, as the rows get bigger and bigger, will create increasingly better approximates of the normal distribution. When we expand (x+y)ⁿ for increasingly big numbers n, there will be increasingly bigger numbers of terms that have closer to equal numbers of x’s and y’s, because there are more ways of getting combinations that way.

But wait there is one more cool pattern…no it’s a lie. There are so many more. This triangle is a tapestry created by weaving the threads of counting. But here is at least one last cool coincidence. I wrote a post about the formula for the sum of natural numbers:

Turns out that the sum of natural numbers pops up when calculating (n choose 2) because

Example: I was at Brew Dog with my colleagues one particularly eventful Friday evening. There were a lot of us there. We were cheers’ing as a big group and someone complained that not everybody had cheers’d with every one, and then Niko said the number of pairs cheers’ing was O(n²) and I said that was an over-approximation, that it was (n choose 2). And then Christina pointed out it was the summation of (n-1) because the first person has to cheers with (n-1) partners, and then when they are out of the mix, the next person has to cheers with (n-2) partners etc. I never thought about (n choose 2) being the arithmetic summation before, but it is clear from Yang Hui’s triangle, as the second lot of numbers is the sequency of sums of natural numbers. (They are called the triangle numbers because you can represent natural numbers as dots making rows of a triangle and if you count the dots for each triangle you have the sum. The pyramid numbers are then the sums of the sums, and unfortunately our geometric visualization stops there.)

¹ Thanks Rany for reminding me “there is something suspicious about 11” over coffee at The Rabbit Café, and telling me about how it generates the normal distribution.
Thanks again to the Justin Kao, the creator of http://mathurl.com