Understanding Pascal’s Triangle

How many ways are there to arrange “ABC“? ABC, ACB, BAC, BCA, CBA, CAB. So 6 different ways. But could we have determined it in a way that didn’t involve us listing all the cases? The answer is yes, and welcome to the wonderful world of combinatorics.

Imagine building each pattern. For the first letter, you may choose A, B, or C. So 3 options. Say we choose A, for our next letter, we only have two choices, B or C. Let’s choose B. Then your final choice is fixed, as C. So the number of patterns possible is $3*2*1$ .

In general, the number of ways to arrange a list of $n$ unique elements is $n*(n-1)*(n-2)...1$ . We sometimes write this as $n!$ , also known as the factorial of n.

But what if they weren’t unique? How many ways are there to rearrange ABB if we don’t distinguish between the Bs?

First, lets consider the problem if we do. How many ways can we rearrange (or permute) AB₁B₂? AB₁B₂, AB₂B₁, B₁AB₂, B₁B₂A, B₂AB₁, B₂B₁A.

Notice how each one that is distinct if we don’t differentiate between Bs has a clone (where the Bs are flopped). This is the key to solving the problem in general: figure out the number of clones and get rid of them.

It’s actually quite easy to figure out how many clones there are. For example, imagine we were trying to find the number of permutations of AAAABC. Well, given a particular permutation, say ABACAA, there are a number of ways we could move the As around… The same number in fact as the number of ways we could permute A₁A₂A₃A₄: $4!$ , the factorial of 4. Now, if we had distinguished between the As, there would have been $6!$ ways to arrange ABACAA. So, including the clones, we have $6!$ possibilities, with $4!$ copies of every unique one. Dividing by the number of duplicates then allows us to get rid of them. So in this case, we divide by $4!$ , this gives us $6!/4!=6*5=30$ .

In general, the number of permutations of a list of length $n$ with $a$ copies of one particular element is $n!/a!$ . Similarly, the number of ways to permute a list of length $n$ with $a$ copies of one element and $b$ of another is $n!/(a!b!)$ . And so on.

Now, one particularly important scenario is a list of length $n$ with $m$ As and $(n-m)$ , that is the rest, as Bs. In fact, it is so important that there is a special way of writing the number of ways to permute that list: $\binom{n}{m}$ . By the above, $\binom{n}{m} = \frac{n!}{m!(n-m)!}$ .

There is a lovely interpretation of this. Pascal’s triangle is constructed by starting with a one and having the elements of each proceeding row be the sum of the ones diagonally up from it, like so:

(Diagram (and subsequent ones) based on Paul Gaborit PGF/TiKz example)

Note that the value of the element in the $m$ th position of the $n$ th row is $\binom{n}{m}$ in the above diagram. This is true in general.

Why is this? Well, notice that each values is the number of paths reaching it. And the position a path reaches is uniquely determined by the number of times it goes left and right. In particular, if it takes $n$ steps and goes right $m$ times, it ends up in the $m$ th position in the $n$ th row.

For example, one can reach $\binom{3}{2}$ by going:

Left, Right, Right
Right, Left, Right
Right, Right, Left

Well, how many different paths are there going to that position? How every many different permutations you can make from RRRR…LLL… : $\binom{n}{m}$ .

$\binom{n}{m}$ is important because it comes into play every time you need to repeatedly choose between two choices. A classic examples is the expansion of a binomial — so called binomial theorem.

Consider $(a+b)^2 = aa + ab + ba + bb = a^2+2ab+b^2$ . It is the sum of all paths choosing between $a$ and $b$ . So the number of each “category” of path is $\binom{2}{m}$ where $m$ is the number of $b$ s.

This generalizes: $(a+b)^n= \binom{n}{0}a^n + ... \binom{n}{m}a^{n-m}b^m ... + \binom{n}{n}b^n$

(Aside: sigma notation is a way of writing the sum of a bunch of things. $\sum_{m=0}^3 m$ is a denser way of writing $0 + 1 + 2 + 3$ .)

In sigma notation, this becomes $(a+b)^n = \sum_{m=0}^n\binom{n}{m}a^{n-m}b^m$ , the well-known .

There’s a lot more to be said here, but I’m leaving it to the exercises. Each one contains some interesting insight, and I spent a lot of time coming up with them. I can’t take full credit for (B) and (C): (B) was inspired by a grade 9 class mate who spent a lot of his time making the described pyramid, while (C) was is based off a comment I read on r/math a few months back.

Exercises:

(A) A line segment, square, and cube, are in some ways different dimension version of the same thing. Let’s call a line a 1-cube, a square a 2-cube, a normal cube a 3-cube. Higher dimensional equivalents exist and are named in he same pattern; for example, a 4D cube or tesseract, can be called a 4-cube.

An $n$ -cube has $2n$ sides, each of which is a $(n-1)$ -cube: a square has 4 sides, a cube 6, and so on. How many $(n-2)$ -cube sides-of-sides does it have? How many $(n-3)$ ?
Why is this the case?
Verify this for a tesseract by looking at the picture in the linked article.

(B) Pascal’s Triangle can be generalized to a pyramid, where we consider the number of downward paths to a point. The first few slices look like:

Draw the next few slices of the pyramid.
Why are the outer sides of the pyramid the same as Pascal’s Triangle?
The sum of the numbers on the $n$ th level of Pascal’s Triangle is $2^n$ because every step each path splits in two, doubling the total number of paths. What is the sum of the numbers on the $n$ th level of Pascal’s pyramid? Why?
What is the formula for $\left( \!\! \begin{array}{c} n\\ i\\ j\\ \end{array} \!\! \right)$ , the value on the nth level of the pyramid, in position i on one axis and j on another.
Why is $\left( \!\! \begin{array}{c} n\\ i\\ j\\ \end{array} \!\! \right)$ the coefficient for $a^ib^jc^{n-i-j}$ in the expansion of $(a+b+c)^n$ ?
Make a “trinomial theorem” that describes the expansion of $(a+b+c)^n$ .
Prove your trinomial theorem using binomial theorem. (Hint: you need to use binomial theorem twice!)

Consider the powers of 11: 1, 11, 121, 1331, 14641… Why are they so similar to the levels of Pascal’s Triangle?
Why does the next term in the sequence, 161051, break this pattern?
Can you come up with another number that would last longer?
Why do the powers of $111$ not look like the pyramid from (B)?
Can you changes the rules that generate Pascal’s Triangle so that the rows look like $102^n$ ?

(D) Draw Pascal’s Triangle. Circle and fill in the odd numbers. The pattern that develops is a fractal called the Sierpinski triangle. Why does it form? What would happen if you did this to the pyramid from (B)?

Diagram by Paul Gaborit

(E) $\binom{a}{b}$ is sometimes said out loud as “ $a$ choose $b$ ” because it is the number of different sets of $b$ objects you can take from a set of size $a$ . For example, $\binom{3}{2}=3$ is “three choose two” in the sense that, given a set of size (or cardinality) 3, $\{a,b,c\}$ , one can get 3 subsets of size 2, $\{a,b\}$ , $\{b,c\}$ , and $\{c,a\}$ .

Why is this the case?
Using B.3, determine the total number of subsets (they can be any size!) of a set of size $a$ there are. Can you come up with a more direct reason there should be that many?

(F) The fact that binomial coefficients are always integers has an interesting implication: $a!b!$ always divides $(a+b)!$ .

Explain how we come to this implication.
Can you prove this theorem?
$a_1, a_2, a_3...$ natural numbers (positive whole numbers) are a partition of a number $n$ if $a_1+ a_2+ a_3... = n$ . Can you generalize this property in terms of partitions?
What does this tell you about the distribution of prime numbers?

Comments On Exercises

You may have noticed that a lot of the questions are “why” questions. That is intentional. I think we should give more “why” questions in math, in general. A “why” question can be given to people who can’t yet construct proofs and a correct answer to a “why” question contains the heart of a proof and, with some work, should be able to be converted into a proof. But the reverse doesn’t hold: it is possible to create a formal proof that is so convoluted one can not convert it into an answer of why the fact you have proved is true.

I’ll write up solutions if there is sufficient interest.

Tags: combinatorics, math, teaching

This entry was posted on August 29, 2011 at 02:56 and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Understanding Pascal’s Triangle”

chrisharrow Says:
August 31, 2011 at 10:27 | Reply
You make some great extensions of Pascal’s Triangle that seem quite natural to me now that I’ve read your post, but I hadn’t considered before.

Your questions are great explorations. Thanks for sharing.

The only constructive criticism I’d offer from my time as a teacher regards your sentence between the first two images: “One quickly notices that the value of the element in the $m^{th}$ position of the $n^{th}$ row is $\binom{n}{m}$ .” As mathematicians, I agree that we see that connection, but almost all of the students I’ve taught have had to be coached into that realization. It is a critical connection, but I don’t think it’s a quick notice for very many
- christopherolah Says:
  September 2, 2011 at 01:57 | Reply
  Thanks for the feedback!
  
  I’ve rewritten this as: “Note that the value of the element in the $m$ th position of the $n$ th row is $\binom{n}{m}$ in the above diagram. This is true in general.”
  
  I didn’t really need them to realize why it was true at that point, just notice that it was. Then I could explain it 🙂
Anonymous Says:
September 1, 2011 at 07:35 | Reply
I second chrisharrow here, both in positives and constrctives.

In the same context I would also say:
“To cancel out the clones, we divide by 4!,” is not so obvious to readers that are new to the problem.

In exercise D you refer to “the pyramide”. If one (like me) has jumped over this exercise he would be confused about this fact. Just mention the, that the pyramid is explained in exercise B…

Jan
- christopherolah Says:
  September 2, 2011 at 02:00 | Reply
  Thanks for the comment Jan! I’ve added several sentences leading up to why that is true:
  
  “Well, given a particular permutation, say ABACAA, there are a number of ways we could move the As around… The same number in fact as the number of ways we could permute A₁A₂A₃A₄: 4!, the factorial of 4. Now, if we had distinguished between the As, there would have been 6! ways to arrange ABACAA. So, including the clones, we have 6! possibilities, with 4! copies of every unique one. Dividing by the number of duplicates then allows us to get rid of them. So in this case, we divide by 4!, this gives us 6!/4!=6*5=30.”
  
  >Just mention the, that the pyramid is explained in exercise B…
  
  Done 🙂