Transcript Pascal3 - Online Directory Western Illinois University

“Some 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?
Triangular numbers
Eleven Cool Things About Pascal’s Triangle
Tetrahedral numbers and the Twelve Days of
Christmas
Solve Two Classic Problems.
A Neat Method to find any Figurate Number
0. What kind of session will this be?
• This session will be less like your typical
teacher in-service workshop or math class,
• and more like
–
–
–
–
A play
A musical performance
Sermon
Trip to a Museum
• I’m going to move quickly.
• I will continually explain things at various
levels.
Answering non-Math Questions in advance
Q: How does this relate to my classroom,
NCTM, AMATYC, ILS, NCLB, …?
A1: Understand it first, then get creative.
A2: Get the handouts and websites at the back.
A3: Communicate with me. I’d like to explore
more answers to this question.
Answering non-Math Questions in advance
Q: Isn’t this just math trivia?
A: No. These are useful mathematical ideas
(that are “deep,” but not hard to grasp)
that can be used to solve many problems.
In particular, basic number sense
problems, probability problems and
problems in computer science.
What kind of session will this be?
I want to look at the beauty of Pascal’s
Triangle and improve understanding by
making connections using various
representations.
2. 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
1+2 +3 +4 +5 +6 +7 +8 +9
Interesting facts about Triangular Numbers
• The Triangular
Numbers are the
Handshake
Numbers
• Which are the
number of sides
and diagonals of
an n-gon.
Number of
People in the
Room
2
Number of
Handshakes
3
3
4
6
5
10
6
15
1
Number of Handshakes
= Number of sides and diagonals of an n-gon.
A
B
E
D
C
Why are the handshake numbers Triangular?
Let’s say we have 5 people: A, B, C, D, E.
Here are the handshakes:
A-B A-C A-D A-E
B-C B-D B-E
C-D C-E
D-E
It’s a Triangle !
T1  1 T2  3 T3  6 T4  10 T5  15
T9  45
Q: Is there some easy way to get these numbers?
A: Yes, take two copies of any triangular
number and put them together…..with multi-link
cubes.
9x10 = 90
9
Take half.
Each
Triangle
has 45.
9+1=10
T9  45
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
Eleven Cool Things About
Pascal’s Triangle
Characterization #1
• First Definition: Get each number in a row
from 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 
For example,
8  8   9 
       
 3  4   4 
Show me
the proof
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 we use the Hockey Stick Principle
to sum up stick numbers.
Now let’s add up triangular numbers (use
the hockey stick principle)….
And we get, the 12 Days of Christmas.
A Tetrahedron.
Characterization #8
The third diagonal are
the tetrahedral
numbers.
Why?
Because we use the Hockey Stick Principle
to sum up triangular numbers.
Tetrahedral Numbers are Cool
Like Triangular Numbers
• Do the same things.
– Find a general formula.
– Add up consecutive Tetrahedral Numbers.
Find a general formula.
Te1  1 Te2  4 Te3  10 Te4  20 Te5  35
Find Ten
Use Six copies of the tetrahedron !
Combine Two Consecutive
Tetrahedrals
• You get a pyramid!
– Wow, which is the sum of squares.
– (left for you to investigate)
Characterization #9
This 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.
How many permutations (arrangements) are
there?
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?…(
Characterization #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
Ball dropping
There are 21 different ways for the ball to
drop through 7 rows of pins and end up in
position 2.
Why?
7
Because position 2 is  
 2
And the dropping ball got to that position by
choosing to go right 2 times (and the rest
left).
Equivalently
To get to Wal-Mart you have to go North 2
blocks and East 5 blocks through a grid of
square blocks.
Wal-Mart
There are 7 choose 2
(or 7 choose 5)
ways to get to
Home
Wal-Mart.
Pascal’s Triangle gives it to you for any size grid!
Characterization #11
The fourth diagonal
lists the number of
quadrilaterals formed
by n points on a
circle.
n
 
 4
The fourth diagonal lists the number of
quadrilaterals formed by n points on a circle.
Why?
Because to get a
quadrilateral
you have to
pick 4.
n
 
 4
Note that each quadrilateral
has two diagonals and hence
contributes one point of
intersection in the interior of
the n-gon.
Characterization #11 note
The fourth diagonal
lists the number of
=
quadrilaterals formed
by n points on a
circle.
n
 
 4
The fourth diagonal
lists the number
intersection points of
diagonals (in the
interior) of an n-gon.
Now to Solve Two Classic Problems
1. If you connect n random points on a
circle, how many regions do you get?
(What is the most number of regions?)
2. If you cut a pizza with n random cuts, how
many regions do you get? (What is the
most number of regions?)
1. If you connect n
random points on
a circle, how
many regions do
you get?
The number of regions in a circle
(or pizza) with cuts
R 1  N L  N I
Number of Regions equals 1 plus Number of
Lines plus Number of Intersection points.
(see the article by E. Maier, January 1988
Mathematics Teacher)
Answer to:
If you connect n random points on a
circle, how many regions do you get?
R 1  N L  N I
n n
R  1      
2
4
   
Answer to:
If you connect n random points on a
circle, how many regions do you get?
n n
R  1      
 2  4
Answer to:
2. If you cut a pizza with n random cuts,
how many regions do you get?
R 1  N L  N I
n
R  1  n   
2
 
Answer to:
If you cut a pizza with n random cuts,
how many regions do you get?
n
R  1  n   
 2
Example:
6 cuts in a pizza
give a maximum
of 22 pieces.
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)
•Resources,
•Thank you.
Jim Olsen
Western Illinois University
[email protected]
faculty.wiu.edu/JR-Olsen/wiu/
Addendum
We wish to show the following:
 n  1  n  1  n 

  
   
 r  1  r   r 
First we will show this for a number example:
n = 5; r = 3.
Therefore, we wish to show:
 4  4  5
       
 2   3   3
 4  4  5
To show  2    3    3 
     
5
We will build the  3  subsets from
 
 4
 4
the  2  subsets and  3  subsets
 
 
The 4 choose 2 subsets are subsets of size 2
from the pool {1, 2, 3, 4}.
The 4 choose 2 subsets are:
become:
{1,2,5}
{1,2}
{1,3}
{1,3,5}
{1,4}
{1,4,5}
{2,3}
{2,3,5}
{2,4}
{2,4,5}
{3,4}
{3,4,5}
5
5
5
5
5
5
This gives us some of the 5 choose 3 subsets!
Note: They all have a “5.”
Add “5” to every subset.
 4  4  5
show  2    3    3 
     
The 4 choose 3 subsets are subsets of size 3
from the pool {1, 2, 3, 4}.
The 4 choose 3 subsets are:
{1,2,3} {1,2,4} {1,3,4} {2,3,4}
This gives us more of the 5 choose 3 subsets!
Note: None have a “5.”
Use these as is.
 4  4  5
show  2    3    3 
     
The 4 choose 2 subsets become:
{1,2,5} {1,3,5} {1,4,5} {2,3,5} {2,4,5} {3,4,5}
The 4 choose 3 subsets are:
{1,2,3} {1,2,4} {1,3,4} {2,3,4}
This does constitute all the 5 choose 3 subsets
because any subset of size 3 from the pool
{1,2,3,4,5} will either be of the first type (have
a 5 and two elements from {1,2,3,4}) or of the
second type (be made of of three elements
from {1,2,3,4,}).
 4  4  5
show  2    3    3 
     
Now, in general,
n
We will build the  r  subsets from
 
 n  1
 n  1
the  r  1  subsets and  r  subsets




The n-1 choose r-1 subsets are subsets of
size r-1 from the pool {x1 , x2 , x3 ,..., xn 1}.
To each of these subsets, add the element x n .
The n-1 choose r subsets are subsets of size r
from the pool {x1 , x2 , x3 ,..., xn 1} .
Use these subsets as is.
Putting all these subsets together we get all the
n choose r subsets.
 n  1  n  1  n 
show  r  1   r    r 

 
  
This establishes:
 n  1  n  1  n 

  
   
 r  1  r   r 
Therefore, Characterization #1 and #2
are equivalent!
Show me
Characterization #3