display | more...

Discovered by French mathematician Blaise Pascal in 1653. Every number in the interior of the triangle is the sum of the two numbers directly above it.

```              01
01  01
01  02  01
01  03  03  01
01  04  06  04  01
01  05  10  10  05  01
01  06  15  20  15  06  01
```
This puppy is thick with cool patterns and other fun facts. Blaise was really onto something. The triangle itself was actually first created by the ancient Chinese, but Pascal is the one who found its patterns. Here's a few of 'em:

The sum of the numbers in any row is equal to 2 raised to the power of the row number.

```20 = 1 = 1
21 = 1+1 = 2
22 = 1+2+1 = 4
23 = 1+3+3+1 = 8
```

If the second number of any row is prime, all other numbers in the row (excluding the ones) are divisible by the prime.

```row 7: 01 07 21 35 35 21 07 01
|  |  |  |  |  |
V  V  V  V  V  V
divisible by 7
```

There is an odd "hockey stick" pattern. Start at a 1 on the side of the triangle. Draw a diagonal line down from the 1, and end it somewhere in the middle of the triangle. The sum of all the numbers in the diagonal will equal the number below the end of your "selection" which is not on the same diagonal itself.

```                01
01  01
01  02  01
01  03  03  01
01  04  06  04  01
01  05  10  10  05  01
01  06  15  20  15  06  01
```

The sums of diagonal rows (shown in alternately bold and plain text) produce the Fibonnacci Sequence.

```                  01 = 1
= 1
01  01 = 2
= 3
01  02  01 = 5
= 8
01  03  03  01 = 13
= 21
01  04  06  04  01 = 34
---
01  05  10  10 ---
---
01  06  15 ---
---
01  07 ---
---
01 ---
```

Pascal's triangle is often drawn with each number in a small hexagon. If you fill in the odd numbers on the triangle and leave the even numbers empty, you'll produce the recursive Sierpinski Triangle fractal. Here's a rather poor approximation of that fractal:

```                          ~<
~B8/
(@V<@%
<@%@%@\$V
<\$\$    VB0
<\$/3@  C@X%B
X@@g@@@%@@%@@0
X\$(          `\$0`
%\$G@X        ^@%G@`
0\$@C@@%      <@@0\$@@`
G\$    `@X    ^@<    X@^
00g0` `\$G\$G  <@G@X  %BG\$^
\$0gV@\$(@@(Bg8V@@<@\$XG00^@@^
@8^^^^^^^^^^^^`^^^^^^^^^^^X@^
`\$g@X                      ~\$G@<
`B\$^Gg%                    <B\$ \$B<
`@G%VCC0%                  /@VVCXV@/
`@g\$   /@B0                /@g8   G\$@(
~@8 g@ C@C~@B              /@/ \$\$ 0@`<@V
^@%8%8CVGC8%G8@            %@%8GV8%G%CGV\$V
<@@%          \$\$@`         C@@<         <@\$G
X@C<@8       `\$g`0\$`       C@<C@/       (@C^\$G
XB/G%%8g     ^BC8%GCB`     0GVCG%\$/     C\$C8%%GB
/@@.   8@8    B@X   (\$@    BB8   `\$\$C   (@@^   g0B
G@X%@^ 0@/@\$ <@%X@X /@/%@^ \$B(0\$ `@%/@X X@XV@^ 8\$(G\$
XBg8BC\$88B8\$g%\$C@0%@%@88@C\$8803@g8@%\$8g@3@g8@3B88\$3@G%
```

I'll put more patterns up here as soon as I can figure out how to describe them with HTML and ASCII. ;)

Interestingly, Pascal did not invent his triangle. Joseph Needham shows (in Science and Civilisation in China) how the triangle appears in a Chinese book (The Precious Mirror of the Elements) that dates from several hundred years before Pascal's birth.

Also related to Pascal's triangle are higher-dimensional versions. The entries in the nth row of the triangle correspond to the coefficients in the binomial expansion of (x+y)n-1:

(x+y)2=(1)x2+(2)xy+(1)y2

(x+y)7=(1)x7+(7)x6y+(21)x5y2+(35)x4y3+(35)x3y4+(21)x2y5+(7)xy6+(1)y7

Similarly, the entries in the nth plane of the tetrahedral version correspond to the coefficients of the trinomial expansion of (x+y+z)n-1:

(x+y+z)3=(1)x3+(3)x2y+(3)xy2+(1)y3+(3)y2z+(3)yz2+(1)z3+(3)z2x+(3)zx2+6xyz

As a triangle, these values appear like so:

1
3 3
3 6 3
1 3 3 1

It may seem that this is simply another Pascal triangle from three directions, but don't be fooled. Each entry is actually the sum of three values in the triangle above it:

1
2 2
1 2 1

Even better, the former triangle can be expressed in terms of successive rows of the 'normal' Pascal triangle:

1 * (1)
3 * (1 1)
3 * (1 2 1)
1 * (1 3 3 1)

For reference, here's a zero-padded (x+y+z)^4 expansion triangle... note that any term in any of these triangles can be generated with the multinomial expansion.

```        01
04  04
06  12  06
04  12  12  04
01  04  06  04  01
```

There are as many dimensions of triangles as one may wish to build. Note also the connection between odd vs. even entries and the text art that appears in Seirpinski Triangle.

One might also find it interesting the relationship of Combinations (nCr), and Pascal's Triangle. For each row, n of the triangle (top row being 0), each element along that row, r, is == nCr.

```          1
1   1
1   2   1
1   3   3   1
1   4   6   4   1 <-- n=4

Combinations of 0: 1
1: empty set

Combinations of 1: 4
1: A
2: B
3: C
4: D

Combinations of 2: 6
1: AB
2: AC
3: AD
4: BC
5: BD
6: CB

Combinations of 3: 4
1: ABC
2: ABD
3: ACD
4: BCD

Combinations of 4: 1
1: ABCD

```

An interesting problem is to determine the number of odd coefficients in the expansion of (x+y)n. Essentially, this reduces to determining the number of odd values in the n-th row of Pascal's Triangle.

One might begin an investigation into this problem by calculating the triangle to a reasonably large number of rows. With such a large triangle, it is possible to begin looking for patterns. However, there is a clever trick to save oneself a lot of work! Since we are only concerned with the entries' even-ness or odd-ness (i.e. their parity), we can just make Pascal's Triangle in modulus 2. That is, we create the triangle in the same way, but count the value of 1+1 as 0. As Uberfetus pointed out above, this results in a pattern like a Sierpinski Triangle.

Now we can start counting the number of ones, which correspond to the odd elements of the original triangle. What we find is a sequence:

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, ...

What to make of a sequence like this? (Caveat: The "first" term is actually t0, because the top row of Pascal's Triangle is the "zero-th".) Some observations:

The second term (t1) is twice the first term.
The second two terms (t2 and t3) are twice the first two terms, respectively.
The second group of four terms are twice the first group of four terms.
...
In general, the second group of 2^n terms are twice the first group of 2^n terms.

Hmm. Clearly there is a nested, fractal-like pattern of doubling present. But how does this help us define explicitly the value of the n-th term? That is, we wish to establish a relation between the lists:

n=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,..., and
tn=1, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 8, 4, 8, 8, 16

Note that the number two is key to the pattern we are investigating. On a hunch, let's rewrite our indices in binary:

n=0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, ...
tn=1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16,...

Do you see it yet? Keep looking.... Yes! In general,

tn=2^(# of ones in the binary representation of n).

This may sound weird, but think about it in relation to the nested pattern of doubling we noticed in the sequence originally. By writing the index in binary, we are implicitly locating it within our fractal structure. Each one in its binary representation is another level of nesting. Since each level represents a doubling, we can just raise 2 to the power of the number of these levels!

To put this back into the context of our original question...

To find the number of odd coefficients in (x+y)n, we write n in binary and count the number of ones. Calling this number p, the number of odd coefficients can be calculated as 2p.

Log in or register to write something here or to contact authors.