Pascal's Simplexes

Higher-dimensional geometry (previously "Polyshapes").

Pascal's Simplexes

Postby pat » Wed Dec 01, 2004 10:12 pm

Suppose we want to figure out the coefficient of a<sup>4</sup>b<sup>2</sup> in the expression (a+b)<sup>6</sup>. One way to do this is to multiply out the polynomial. A simpler way is to write out the first seven rows of Pascal's triangle and look at the third or the fifth entry. (I'm going to write it on its side both for convenience and for something up my sleeve...).
Code: Select all
1  1  1  1  1  1  1 ...
1  2  3  4  5  6 ...
1  3  6 10 15 ...
1  4 10 20 ...
1  5 15 ...
1  6 ...
1 ...
...

Now, because I wrote it on its side, the coefficients of the terms in (a+b)<sup>n</sup> are in the n+1-th diagonal. So, for example:
(a+b)<sup>3</sup> = a<sup>3</sup> + 3a<sup>2</sup>b + 3ab</sup>2</sup> + b<sup>3</sup>.

For those that haven't seen Pascal's triangle before, each entry is the sum of the entry above it and the entry to its left.

You can think of the n-th diagonal as the coefficients of the terms in (a+b)<sup>(n-1)</sup> so long as you consider the j-th column to indicate that a is to the (j-1)-th power and the k-th row to indicate that b is to the (k-1)-th power.

Anyhow, that's all well and good. But, what if we had (a+b+c)<sup>n</sup>?

Before we get to that, let's look at the easier case where we have (a)<sup>n</sup>. Then, the coefficients are:
Code: Select all
1 1 1 1 1 1 ...


That is exactly the same as the first row in Pascal's triangle if you write Pascal's triangle on its side as I did.

Now, let's get back to (a+b+c)<sup>n</sup>. Let's try a few cases.
(a+b+c)<sup>1</sup> yields a + b + c. This means the coefficients are 1, 1, and 1. For n = 2, we get a<sup>2</sup> + b<sup>2</sup> + c<sup>2</sup> + 2ab + 2ac + 2bc. This means we have coefficients 1, 1, 1, 2, 2, 2. For n = 3, we get coefficients 1, 1, 1, 3, 3, 3, 3, 3, 3, and 6.
For n = 4, we get coefficients 1, 1, 1, 4, 4, 4, 4, 4, 4, 6, 6, 6, 12, 12, and 12. What's the pattern here?

If we look at the diagonals of Pascal's triangle. And, if we think of putting a box around each number, then we can start with an unlablelled quarter-plane full of boxen. We can fill in the top-corner with a 1. Then, we can fill in each blank box with the sum of the box adjacent above it and the box adjacent to its left. Lather, rinse, repeat:
Image

If we repeat this process except in three-dimensions, then we'll start with an octant (1/8-th of a realm) full of boxen. We'll do the same thing. We'll fill in the corner with a one. Then, we'll fill in all of the boxen with the sum of its neighbors above, to the left, and behind. We'll end up starting off like this:
Image

You'll notice that the axises are the coefficients from the a<sup>n</sup> case and the axis-planes are exactly the Pascal triangle from the previous diagram.

You'll also notice that the first diagonal plane through a box center goes through the center of a box labelled 1. The second diagonal plane through box centers goes through the centers of boxen labelled 1, 1, and 1. The third goes through the centers of boxen labelled 1, 1, 1, 2, 2, and 2. The fourth goes through the centers of boxen labelled 1, 1, 1, 3, 3, 3, 3, 3, 3, and 6. The fifth goes through the centers of boxen labelled 1, 1, 1, 4, 4, 4, 4, 4, 4, 6, 6, 6, 12, 12, and 12. Do these look familiar? These were the n = 0, 1, 2, 3, and 4 cases of (a+b+c)<sup>n</sup>.

You can think of the n-th diagonal plane through box centers as the coefficients of the terms in (a+b+c)<sup>(n-1)</sup> so long as you consider the j-th column to indicate that a is to the (j-1)-th power and the k-th row to indicate that b is to the (k-1)-th power and the m-th level to indicate that c is to the (m-1)-th power.

It's relatively straightforward to prove by induction that if you carry this process out in k dimensions, then you're building the coefficients of (a<sub>1</sub>+a<sub>2</sub>+...+a<sub>k</sub>)<sup>n</sup>.

Now, this post is already getting long, so I'm going to cut out here before I get to what's up my sleeve. Actually, I suppose this was already somewhat up my sleeve since cubes stack nicely in all dimensions. But, alas, I have something else up my sleeve.... I'll get to that in a moment.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Up my sleeve...

Postby pat » Wed Dec 01, 2004 11:11 pm

Now, that stuff is cool, in and of itself. But, here's what I really wanted to get to.

When I was first trying to figure out the above, I was trying to work with circles set out in equilateral triangles instead of boxes set out in 45-45-90 triangles. But, things got a little wiggy on me when I moved up to three dimensions. The first few pyramids are made up of 1 ball, 4 balls, 10 balls, and 20 balls. It wasn't immediately clear when you went to add 6 more balls to the 4-ball pyramid how to clearly (algorithmically) describe how to do it so that you still ended up with a pyramid.

What I came up with was very recursive. Start with the smallest pyramid---one ball. Now, think of that as a triangle. Make the next biggest triangle. To make that next biggest triangle, think of it as one-simplex (a line segment). Make the next biggest line-segment. Put your old triangle on top. Now, you've got a three-ball triangle. Put your old pyramid on top. Now, you've got the next biggest pyramid---a four-ball pyramid.

Now, make the next biggest triangle. Do this by starting with the last base you made for your pyramid. Then, take the last base that you made for that triangle and think of it as a one-simplex. Make the next biggest one-simplex. Put your old triangle on top. Now, put your old pyramid on top.
Image

So, it started to occur to me, that the number of balls in the k-th pyramid in the sequence (the k-th smallest pyramid) depended on the number of balls in the k-1-th pyramid in the sequence and the number of balls in the k-th smallest triangle. The number of balls in the k-th smallest triangle depended on the number of balls in the (k-1)-th smallest triangle and the k-th one-simplex.

And, since the smallest pyramid in any number of dimensions has one ball in it and since the k-th one-simplex has k balls in it, if we chart the number of balls as a function of dimension d and order in the sequence k, then we get the following chart. The number in the d-th row and k-th column represents the number of balls in the k-th smallest d-dimensional pyramid.
Code: Select all
1  2  3  4  5  6  7 ...
1  3  6 10 15 21 ...
1  4 10 20 35 ...
1  5 15 35 ...
1  6 21 ...
1  7 ...
1 ...
...


If we go one step further and say that all 0-dimensional simplexes are made up of one ball (regardless of how "big" the simplex is), then we have exactly Pascal's triangle (of course, now with the (d+1)-th row being the d-dimensional simplexen).
Code: Select all
1  1  1  1  1  1  1  1 ...
1  2  3  4  5  6  7 ...
1  3  6 10 15 21 ...
1  4 10 20 35 ...
1  5 15 35 ...
1  6 21 ...
1  7 ...
1 ...
...


So, that's what was up my sleeve. I thought it was pretty cool. But, there's something else that I thought particularly intriguing.

Pascal's triangle is symmetric across the diagonal. That means that there are the same number of balls in the k-th d-dimensional pyramid as there are in the (d+1)-th (k-1)-th dimensional pyramid.

Why?

I wanted it to be because the simplex is self-dual. But, it's only self-dual within its own dimension. Though, from this, it kind of seems that it has a dimension-volume duality going, too.

With my cube-packing version of Pascal's triangle, this is saying that in: N<sup>d</sup> (where N is the counting numbers: 1, 2, 3, 4, 5, ... ), the first k diagonal hyperplanes (diagonal as in perpendicular to (1,1,1,1,...,1)) encompass the same number of lattice points as the first (d+1) diagonal hyperplanes in N<sup>(k-1)</sup>. (with the assumption that N<sup>0</sup> isn't empty and contains only one point).

I'm going to post this in the Mathematics LiveJournal, too.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Postby Paul » Thu Dec 02, 2004 8:33 pm

Hello Pat,

I'm not sure I fully understand... but, is what you're doing with the cubes related to the multinomial theorem?

Also... that graphics software you used to produce that image of the 3D cubes on top, and to the side, of each other... what is it? I hoping it's not that Mac software... that doesn't have a Windows port...
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm

Postby pat » Thu Dec 02, 2004 8:35 pm

Yes, the stuff with the cubes is the multinomial theorem.

And, yes, the program that I used to make the images was OmniGraffle which has no windows port.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN


Return to Other Geometry

Who is online

Users browsing this forum: Baidu [Spider] and 0 guests