Tuesday, July 10, 2018

Paths, Combinations, Simplices, and Sums

This summer I've been studying "Pascal's" triangle a lot. Here's what I learned:

1. Paths

I used to think my three-part lesson on binomial expansion was pretty slick. We would start with (a+b)^0 and work up, applying our recently learned (or re-learned) polynomial multiplication skills. (a+b)^4 is a lot of fun because some students work it out as (a+b)(a+b)^3 while others use (a+b)^2(a+b)^2. Then there is a sudden break in the lesson and we start computing the rows of "Pascal's" triangle. After we get pretty far I ask the class why I would have us write out all these numbers. Could they help us with our powers of (a+b)? It takes a while before any light bulbs turn on. As they flicker on, I ask my "enlightened" students to try writing out the next power of (a+b) using the pattern they see.

The part of the lesson that bothers me now is my introduction of "Pascal's" triangle and the superficiality of our connection between the entries in the triangle and the coefficients in the binomial expansion. I would start by writing out the first few rows of the triangle and then either just tell students the rule for generating further rows, or ask students if they could see a pattern. And later, when students saw the connection to binomial expansion, we would just blindly exploit this magic coincidence instead of seeking to understand it.

It is more natural to start with the structure of "Pascal's" triangle and then ask students a question that enables them to fill in all the numbers on their own. The structure we start with is an infinite complete binary tree and the question we ask of a given node is: how many paths descend to it from the root node? But we won't get so wordy with students when we can just show them a picture:
They will be able to fill in the entries of the triangle and then even notice and justify the rule. Every path to a point either passes through its upper left neighbor or its upper right neighbor. So to figure out the number of paths to a point, add up the number of paths to each of its upper neighbors.

To connect these "path numbers" to the binomial expansion coefficients, I was inspired by an old blog post by Sam Shah (https://samjshah.com/2016/09/29/binomial-expansion/) and also a comment by Scott Farrar (@farrarscott). Every path can be thought of as a sequence of choices between left and right.
Similarly, every term in the full expansion of (L + R)^n can be thought of as a sequence of choices between left and right. Notice how the above triangle illustrates the expansion of, say, (L+R)^3:
(LL + LR + RL + RR)(L+R)
(LL)(L+R) + (LR+RL)(L+R) + (RR)(L+R)
Constructing "Pascal's" triangle using paths through a binary tree helps develop the connection with binomial expansion. It is also easy to see that the sum of row n is 2^n, since there are 2^n ways to make n choices between left and right.

By the way, why should we call it "Pascal's" triangle when we knew about it long before Blaise Pascal?

2. Combinations

In dating apps we swipe left to reject and swipe right to express interest. Along these lines, taking a path through our binary tree can be seen as generating a set of objects. Each choice between left and right becomes a choice to exclude or include some particular object. Compare this diagram with the one above:
For another way to see the correspondence, consider that a binary path can be determined by giving the positions of just the right swipes. We could communicate LRRL by indicating that the only right swipes are the second and third. And if our second and third objects are b and c, LRRL gives us the set {b,c}.
Things start to get interesting if we think of our sets as literal boxes and consider how we might stack them. Imagine constructing the triangle by taking the stack of boxes to your left and putting a certain type of object in every box, leaving the stack to your right alone, and then pushing these two stacks together. Here is one way we could stack our boxes:
This drawing shows a few more stacks of boxes without any labels or arrows in the way:
Extending this drawing to the left would be easy. There is a constant sequence of unit cubes, a successively taller sequence of simple stacks, a sequence of triangular staircases, and finally a sequence of tetrahedral stacks. Just as we could not construct the tetrahedral stacks out of squares, extending this drawing to the right any further would exhaust the three dimensions of our cubes. We might have some luck if we switched from cubes to tesseracts, but there are other ways to get a glimpse these higher-dimensional analogues.

3. Simplices

One option is to switch from boxes/cubes/tesseracts to points. And instead of stacking them (which meant unifying certain faces for the cubes) we'll draw line segments between them. If we do this we'll end up with simplexical figures. I hadn't much idea what simplices were until around a month ago, which is probably why I failed the second semester of Honors Analysis.

Basically, the simplices are to the triangle what the hypercubes are to the square. If you have an n-cube you can make an (n+1)-cube. Just copy your n-cube by translating it along a new dimension and then draw a line segment between each point of your n-cube and its image in the copy. So a 0-cube (point) connects to another 0-cube (point) to make a 1-cube (line segment). A 1-cube connects to another 1-cube to make a 2-cube (square). A 2-cube gets another 2-cube to make a 3-cube (cube).
Similarly, if you have an n-simplex you can make an (n+1)-simplex. Just find a point outside your n-dimensional system and draw a line segment between each point of your n-simplex and this new point. Connect a point to all the points in a 0-simplex (point) to make a 1-simplex (line segment). Connect a point to all the points in a 1-simplex to make a 2-simplex (triangle). Join a point to a 2-simplex to make a 3-simplex (tetrahedron). And the tetrahedron becomes a 4-simplex (5-cell).
Here is another version of our drawing with simplices. Extending the drawing to the right more is left as an exercise for the reader!
It's possible to "see" the higher-dimensional simplexical numbers by collapsing everything down a dimension. We can start by collapsing line segments into numbers.
We can continue this process by collapsing stacks of numbers into triangular numbers.
We could continue the process indefinitely, next collapsing stacks of triangular numbers to make tetrahedral numbers.

4. Sums

Once we see the triangular figures as stacks of line segments, the tetrahedral figures as stacks of triangular figures, and in general the (n+1)-simplexical figures as stacks of n-simplexical figures, we are ready to view the n-simplexical numbers as sums. 1 + 2 + 3 + 4 + 5 is T(5) = 15, the fifth triangular number. Similarly, T(1) + T(2) + T(3) + T(4) + T(5) is 35, the fifth tetrahedral number. Continuing this pattern, the sum of the first five tetrahedral numbers is 70, the fifth 4-simplexical number. Try locating these numbers on "Pascal's" triangle. We can make a general statement:

The sum of the first m n-simplexical numbers
is the mth (n+1)-simplexical number.

As a final thought, consider writing the entries of "Pascal's" triangle using sigma notation. We can then write a funny-looking formula.
That concludes my thoughts about "Pascal's" triangle. Please let me know if you can offer more insight, correct any of my mistakes, or are inspired to do any interesting math!