Transcript Pascal-II-1 - Online Directory Western Illinois University

“More Really Cool Things
Happening in Pascal’s Triangle”
Jim Olsen
Western Illinois University
Outline
0.
1.
2.
3.
4.
5.
What kind of session will this be?
Review of some points from the first talk on
Pascal’s Triangle and Counting Toothpicks in
the Twelve Days of Christmas Tetrahedron
Two Questions posed.
Characterizations involving Tower of Hanoi,
Sierpinski, and _______ and _______.
A couple more interesting characterizations.
Two Questions solved.
0. What kind of session will this be?
• This session will be less like your typical
teacher in-service workshop or math class.
• Want to look at some big ideas and make
some connections.
• I will continually explain things at various
levels and varying amounts of detail.
• Resources are available, if you want more.
• Your creativity and further discussion will
connect this to lesson planning, NCLB,
standards, etc.
1. Review
Triangular numbers
T1  1 T2  3 T3  6 T4  10 T5  15
(Review)
Let’s Build
the 9th
Triangular
Number
T9  45
1+2 +3 +4 +5 +6 +7 +8 +9
(Review)
n(n+1)
Take half.
n
(Review)
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
Eleven Characterizations
• Char. #1: First Definition: Get each number in
a row from the two numbers diagonally above
it (and begin and end each row with 1). This
is the standard way to generate Pascal’s
Triangle.
(Review)
• Char. #2: Second Definition: A Table of
Combinations or Numbers of Subsets
(Characterization #1 and characterization #2
can be shown to be equivalent)
• Char. #3: Symmetry
9 9
    
 2 7
 n  n 
   

r  n  r
(Review)
5
5 choose 2     10
 2
10 subsets
10 
10 choose 7     120
7
(Review)
120 subsets
• Char. #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
(Review)
• Char. #5: The Hockey Stick Principle
(Review)
• Char. #6: The first diagonal are the
“stick” numbers.
• Char. #7: second diagonal are the
triangular numbers.
(Review)
• Char. #8: The third
diagonal are the
tetrahedral numbers.
(Review)
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?
(Review)
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!
• Char.#9: This is actually a table of
permutations (permutations with repetitions).
• Char. #10: Imagine a pin at each location in
the first n rows of Pascal’s Triangle (row #0
to #n-1). Imagine a ball being dropped from
the top. At each pin the ball will go left or
right.
The numbers in row n are the number of
different ways a ball being dropped from the
top can get to that location.
Row 7 >> 1 7 21 35 35 21 7 1
Char. #11: The fourth
diagonal lists the number of
quadrilaterals formed by n
points on a circle.
n
 
 4
(Review)
2. Two Questions posed
1. What is the sum of the squares of odd
numbers (or squares of even numbers)?
1  3  5  ...  (2n  1)  ?
2
2
2
2
2. What is the difference of the squares of
two consecutive triangular numbers?
Tn  T
2
2
n 1
?
3. 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/cgi-bin/organics/pascalform
Characterization #14
Sierpinski’s Gasket, with 2n rows, provides a
solution (and the best solution) to the Tower of
Hanoi problem with n disks.
At each (red) colored node in Sierpinski’s Gasket
assign an n-tuple of 1’s, 2’s, and 3’s (numbers stand
for the pin/tower number).
The first number in the n-tuple tells where the a-disk
goes (the smallest disk).
The second number in the n-tuple tells where the bdisk goes (the second disk).
Etc.
Maybe we should call it
Sierpinski’s Wire Frame
The solution to Tower of Hanoi is given by moving from
the top node to the lower right corner.
The solution to Tower of Hanoi is given by moving from
the top node to the lower right corner.
Ruler Markings
Solution to Tower of Hanoi
Sierpinski 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
Solution to Tower of Hanoi
1
10
11
100
101
110
111
Binary Numbers
Sierpinski Wire Frame
4. A Couple More Interesting
Characterizations.
Characterization #15
By adding up numbers on “diagonals” in Pascal’s
Triangle, you get the Fibonacci numbers.
This works
because of
Characterization
#1 (and the fact
that rows begin
and end with 1).
Characterization #16
To get the numbers in any row (row n), start
with 1 and successively multiply by
n
,
1
n 1
,
2
n2
,
3
n3
1
,...,
4
n
For example, to generate row 6.
1
6

1
5

2
4

3
3

4
2

5
1

6
1
6
15
20
15
6
1
5. Two Questions Answered
1. What is the sum of the squares of odd
numbers (or squares of even numbers)?
1  3  5  ...  (2n  1)  ?
2
2
2
2
2  4  6  ...  (2n)  ?
2
2
2
2
See Model.
Answer: A tetrahedron. In fact, Te2 n 1 or
Te2n
Two Questions Answered (cont.)
2. What is the difference of the squares of
two consecutive triangular numbers?
Tn  T
2
2
n 1
?
See Model.
Answer: A cube. In fact, n3.
More Information
http://www.wiu.edu/users/mfjro1/wiu/tea/pascal-tri.htm
•Thank you.
Jim Olsen
Western Illinois University
[email protected]
faculty.wiu.edu/JR-Olsen/wiu/