Transcript Pascal-For-Math 406.p+ - Online Directory Western Illinois University

“Some Really Cool Things
Happening in Pascal’s
Triangle”
Jim Olsen
Western Illinois University
This version is compiled for Math 406.
Outline
1.
2.
3.
Triangular Numbers, Initial
Characterizations of the elements of
Pascal’s Triangle, other Figurate
Numbers, and Tetrahedral numbers.
Tower of Hanoi Connections in Pascal’s
Triangle
Catalan numbers in Pascal’s Triangle
1. Triangular numbers
T1  1 T2  3 T3  6 T4  10 T5  15
In General, there are Polygonal Numbers
Or Figurate Numbers
Example: The pentagonal numbers are
1, 5, 12, 22, …
Let’s Build
the 9th
Triangular
Number
T9  45
1+2 +3 +4 +5 +6 +7 +8 +9
n(n+1)
Take half.
n
Each
Triangle
has
n(n+1)/2
n+1
n(n  1)
Tn 
2
Another Cool Thing about
Triangular Numbers
Put any triangular number together with the
next bigger (or next smaller).
And you get a Square!
T8  T9  9  81
2
Tn 1  Tn  n
2
Some Basic Characterizations of
Pascal’s Triangle
Characterization #1
• First Definition: Get each number in a row by
adding the two numbers diagonally above it
(and begin and end each row with 1).
Example: To get the 5th element in row #7, you
add the 4th and 5th element in row #6.
Characterization #2
• Second Definition: A Table of
Combinations or Numbers of Subsets
• But why would the number of combinations
be the same as the number of subsets?
etc.
etc.
Five Choose Two
5
 
 2
{A, B}
{A,
{A,
{A, B}
C}
{A, C}
D}
{A, D}
etc.
{A, B, C, D, E}
etc.
5
Form subsets of size Two  Five Choose Two  2 
• Therefore, the number of combinations of a
certain size is the same as the number of
subsets of that size.
5
5 choose 2     10
 2
10 subsets
10 
10 choose 7     120
7
120 subsets
Characterization #1 and
characterization #2 are equivalent,
because
 n  1  n  1  n 

  
   
 r  1  r   r 
Characterization #3
Symmetry or
“Now you have it,
now you don’t.”
9 9
    
 2 7
 n  n 
   

r  n  r
Characterization #4
The total of row n
= the Total Number of
Subsets (from a set of size
n)
=2n
1  5  10  10  5  1  2 5  32
n n n
n
              2 n
 0  1  2
n
Why?
Characterization #5
The Hockey Stick Principle
The Hockey Stick Principle
Characterization #6
The first diagonal are
the “stick” numbers.
…boring, but a lead-in
to…
Characterization #7
The second diagonal
are the triangular
numbers.
Why?
Because of summing up stick numbers and
the Hockey Stick Principle
Triangular Number Properties
Relationships between Triangular and Hexagonal
Numbers….decompose a hexagonal number into
4 triangular numbers.
Notation
Tn = nth Triangular number
Hn = nth Hexagonal number
Decompose a hexagonal number into 4 triangular numbers.
H n  1  5  ...  (4n  3)
Tn  1  2  ...  n
H n  Tn  3Tn 1
H n  T2 n 1
H n  n(2n  1)
A Neat Method to Find Any
Figurate Number
Number example:
Let’s find the 6th pentagonal number.
The
th
6
Pentagonal Number is:
• Polygonal numbers always
begin with 1.
• Now look at the “Sticks.”
– There are 4 sticks
– and they are 5 long.
• Now look at the triangles!
– There are 3 triangles.
– and they are 4 high.
1 + 5x4 + T4x3
1+20+30 = 51
The
th
k
n-gonal Number is:
• Polygonal numbers always
begin with 1.
• Now look at the “Sticks.”
– There are n-1 sticks
– and they are k-1 long.
• Now look at the triangles!
– There are n-2 triangles.
– and they are k-2 high.
1 + (k-1)x(n-1) + Tk-2x(n-2)
Now let’s add up triangular numbers
(use the hockey stick principle)….
A Tetrahedron.
And we get, the 12 Days of Christmas.
Characterization #8
The third diagonal are
the tetrahedral
numbers.
12 Days of Christmas
Why?
Because we use the Hockey Stick Principle
to sum up triangular numbers.
Formula for the nth tetrahedral number
…see it…
From
Proofs
Without
Words
Characterization #9
Pascal’s triangle is actually a table of permutations.
Permutations with repetitions. Two types of
objects that need to be arranged.
For Example, let’s say
we have 2 Red tiles and
3 Blue tiles and we want
to arrange all 5 tiles.
There are 10 permutations.
Note that this is also 5 choose 2.
Why?
Because to arrange the tiles, you
need to choose 2 places for the
red tiles (and fill in the rest).
Or, by symmetry?…(
2. Characterizations involving
Tower of Hanoi, Sierpinski,
and _______ and _______.
• Solve Tower of Hanoi.
• What do we know? Brainstorm.
• http://www.mazeworks.com/hanoi/index.htm
Solutions to Tower of Hanoi
Disks
Moves
Needed
1
1
a
2
3
aba
3
7
aba c aba
4
15
aba c aba D aba c aba
5
31
aba c aba D aba c aba E aba c aba D aba c aba
Sequence
Characterization #12
The sum of the first n rows of Pascal’s Triangle
(which are rows 0 to n-1) is the number of
moves needed to move n disks from one peg
to another in the Tower of Hanoi.
Notes:
• The sum of the first n rows of Pascal’s
Triangle (which are rows 0 to n-1) is one
less than the sum of the nth row. (by
Char.#4)
• Equivalently: 20  21  2 2  ...  2 n 1  2 n  1
Look at the Sequence as the disks
Disks
Moves
Needed
2
3
Sequence
aba
Look at the Sequence as the disks
Disks
Moves
Needed
Sequence
3
7
aba c aba
What does it look like?
Look at the Sequence as the disks
A ruler!
Solutions to Tower of Hanoi
Can you see the ruler markings?
Disks
Moves
Needed
1
1
a
2
3
aba
3
7
aba c aba
4
15
aba c aba D aba c aba
5
31
aba c aba D aba c aba E aba c aba D aba c aba
Sequence
Ruler Markings
Solution to Tower of Hanoi
What is Sierpinski’s Gasket?
http://www.shodor.org/interactivate/activities/gasket/
It is a fractal because it is self-similar.
More Sierpinski Gasket/Triangle
Applets and Graphics
http://howdyyall.com/Triangles/ShowFrame/ShowGif.cfm
http://www.arcytech.org/java/fractals/sierpinski.shtml
by Paul Bourke
Vladimir Litt's, seventh grade pre-algebra class
from Pacoima Middle School Pacoima,
California created the most amazing Sierpinski
Triangle.
http://math.rice.edu/%7Elanius/frac/pacoima.html
Characterization #13
If you color the odd numbers red and the even
numbers black in Pascal’s Triangle, you get a
(red) Sierpinski Gasket.
http://www.cecm.sfu.ca/organics/papers/granville/support/p
ascalform.html
Ruler Markings
Solution to Tower of Hanoi
Sierpinski Gasket/Wire Frame
…But isn’t all of this
• Yes/No…..On/off
• Binary
• Base Two
Characterization #12.1
The sum of the first n rows of Pascal’s Triangle
(which are rows 0 to n-1) is the number of
non-zero base-2 numbers with n digits.
Count in
Base-2
1
Digit
2
Digits
3
Digits
1
1
10
11
1
10
11
100
101
110
111
What Patterns
Do You See?
How can this list
be used to solve
Tower of Hanoi?
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
Binary Number List Solves Hanoi
Using the list of non-zero base-2
numbers with n digits. When:
• The 20 (rightmost) number changes
to a 1, move disk a (smallest disk).
• The 21 number changes to a 1, move
disk b (second smallest disk).
• The 22 number changes to a 1, move
disk c (third smallest disk).
• Etc.
abaCaba
3
Digits
1
10
11
100
101
110
111
Ruler Markings
1
10
11
100
101
110
111
Solution to Tower of Hanoi
Binary Numbers
Sierpinski Gasket/ Wire Frame
Catalan numbers are also in Pascal’s Triangle
The Catalan numbers are a sequence of natural
numbers that occur in numerous counting
problems, often involving recursively defined
objects.
They are named for the Belgian mathematician
Eugène Charles Catalan (1814–1894).
The first Catalan numbers 1, 1, 2, 5, 14, 42,132,
429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845…
(“numerous” is an understatement)
A Fun Way to Count the Toothpicks in the 12
Days of Christmas Tetrahedron
Organize the marshmallows (nodes) into
categories, by the number of toothpicks
coming out of the marshmallow.
What are the categories?
Category of
Nodes
Number of
Nodes
Number of
Toothpicks
from each
Product
Corners
Edges
4
6x10
3
6
12
360
Faces
4xT9
9
1620
Interior
Te8
12
1440
Total: 3432
But….
This double counts, so there are 1716 toothpicks!
Thank You
Jim Olsen
Western Illinois University
[email protected]
www.wiu.edu/users/mfjro1/wiu/index.htm
www.wiu.edu/users/mfjro1/wiu/tea/pascal-tri.htm