Transcript faculty.ithaca.edu

From Counting to Pascal:
A Journey through Number Theory,
Geometry, and Calculus
NYS Master Teachers
March 9, 2015
Dave Brown – [email protected]
Slides available at
http://faculty.ithaca.edu/dabrown/docs/masterteachers/
Goals
• Use counting (combinatorics) to generate
patterns
• Link counting patterns to algebra, geometry,
trigonometry, & calculus
• Explore patterns in counting structures
• Draw connections among various branches of
math
• Learn some discrete mathematics
Dividing Rectangles
• Start with a simple subdividing game.
• Divide rectangles into shorter rectangles and count.
• For example, we can divide a length 3 rectangle
1
1
1
2
1
1
2
These two are considered different
• How many divisions of a length 3 rectangle are possible?
• Explore subdivisions using Activity 1.
Dividing Rectangles
• What strategies can we use to list ALL possible divisions?
• Important: What is your process?
• Two main ideas in counting:
• Make sure we have counted everything
• Make sure nothing has been counted twice
Dividing Rectangles
1. Constructive approach
Systematically build all divisions of a given length
2. Recursive approach
Use divisions of shorter rectangles to build longer one
Dividing Rectangles
1. Constructive approach
Systematically build all divisions of a given length
• Suppose you want to find all divisions of rectangle of length 10
• If we want all three block divisions, we can use 2 separators in any of 9 spots.
3-block
5-block
2-block
1
2-block
1
2 3 4
4-block
2 3 4
5 6 7
8 9
4-block
5 6 7
8 9
Dividing Rectangles
1. Constructive approach
Systematically build all divisions of a given length
• Suppose you want to find all divisions of rectangle of length 10
• If we want all 5 block divisions, how many separators do we use?
• 4 separators will give us all divisions into 5 blocks
1
2 3 4
5 6 7
8 9
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
• Every division has a final (rightmost) block of length 1 OR of length greater than 1
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
• Remove all final blocks of length 1
• Do you get all rectangles of length 4?
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
• What about the other 8 length 5 rectangles?
• Can we do anything to final blocks to get all rectangles of length 4?
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
• We get all 8 length 4 rectangles by either removing the final 1-blocks, Or
• We get all 8 length 4 rectangles by shrinking the final blocks bigger than 1
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
• Reverse the logic.
• How do you get all of the length 5 rectangles from two copies of the length 4 rectangles?
Add 1-blocks
to the end
Lengthen the end-block
by 1
Dividing Rectangles
2. Recursive approach
Use divisions of shorter rectangles to build longer one
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
# of different
divisions
1
2
3
4
5
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
# of different
divisions
1
2
3
4
5
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
# of different
divisions
1
2
3
4
5
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
3
# of different
divisions
1
2
4
4
5
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
3
4
# of different
divisions
1
2
4
8
5
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
3
4
5
# of different
divisions
1
2
4
8
16
n
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
3
4
5
n
# of different
divisions
1
2
4
8
16
2n-1
• How do we prove this?
1. Constructive approach – separators
• For the length 10 rectangle, in how many places could we use separators?
• 9 locations (can use 0-9 separators)
• In each location, you can either use a separator or not
• So, there are 29 decisions about dividing to make; hence, 29 divisions
• How does this generalize to rectangles of length n?
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
Rectangle
Length
1
2
3
4
5
n
# of different
divisions
1
2
4
8
16
2n-1
• How do we prove this?
2. Recursive approach – idea of building up
• For the length 5 rectangles, how many ended with 1-blocks vs not?
• What is the relationship btw # of length 5 rectangles and # of length 4?
• #(length 5) = 2*#(length 4)
• Similarly, #(length 4) = 2*#(length 3)
• This pattern continues
• How does it help get to the formula?
Number of Divisions of Length n
• How many divisions of a rectangle of length n are possible?
2.
Rectangle
Length
1
2
3
4
5
n
# of different
divisions
1
2
4
8
16
2n-1
Recursive approach – idea of building up
• Reverse this recursive count!
• #(length 1) = 1 = 20
• #(length 2) = 2*#(length 1) = 2 = 21
• #(length 3) = 2*#(length 2) = 4 = 22
• #(length 4) = 2*#(length 3) = 8 = 23
• Continue via induction
• #(length n) = 2*#(length n-1) = 2*2n-2 = 2n-1
A Finer Counting
• Consider the number of blocks in each division.
• For example, in how many ways can a length 3 rectangle be broken
into 2 blocks?
1
1
1
2
1
• Explore block counts in Activity 2.
1
2
3
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
Rectangle of
length 3
Rectangle of
length 4
Rectangle of
length 5
Rectangle of
length 6
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
Rectangle of
length 4
Rectangle of
length 5
Rectangle of
length 6
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
Rectangle of
length 5
Rectangle of
length 6
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
Rectangle of
length 6
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
Pascal’s Triangle!
Pascal’s Triangle
Named after Blaise Pascal (1623-1662)
but known much earlier.
Pascal’s Triangle
Row 0
Row 1
Row 2
Row 3
• Pas(0,0) = 1
• Pas(1,0) = Pas(1,1) = 1
• Pas(2,0) = Pas(2,2) = 1,
Pas(2,1) = 1 + 1 = Pas(1,0) + Pas(1,1)
• Pas(3,0) = Pas(3,3) = 1,
Pas(3,1) = Pas(2,0) + Pas(2,1)
Pas(3,2) = Pas(2,1) + Pas(2,2)
Pas(n,0) = Pas(n,n) = 1
Pas(n,k) = Pas(n-1,k-1) + Pas(n-1,k)
How do we relate this to the block divisions?
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
A Finer Counting
# of blocks in
Rectangle
1
2
3
4
5
6
Rectangle of
length 1
Pas(0,0)
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
A Finer Counting
# of blocks in
Rectangle
1
2
3
4
5
6
Rectangle of
length 1
Pas(0,0)
0
0
0
0
0
Rectangle of
length 2
Pas(1,0)
Pas(1,1)
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
A Finer Counting
# of blocks in
Rectangle
1
2
3
4
5
6
Rectangle of
length 1
Pas(0,0)
0
0
0
0
0
Rectangle of
length 2
Pas(1,0)
Pas(1,1)
0
0
0
0
Rectangle of
length 3
Pas(2,0)
Pas(2,1)
Pas(2,2)
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
A Finer Counting
# of blocks in
Rectangle
1
2
3
4
5
6
Rectangle of
length 1
Pas(0,0)
0
0
0
0
0
Rectangle of
length 2
Pas(1,0)
Pas(1,1)
0
0
0
0
Rectangle of
length 3
Pas(2,0)
Pas(2,1)
Pas(2,2)
0
0
0
Rectangle of
length 4
Pas(3,0)
Pas(3,1)
Pas(3,2)
Pas(3,3)
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
The # of ways to divide a rectangle of length n into k blocks is
Pas(n-1,k-1)
Going to Work
• Iva Jean lives 16 blocks from work
• Each day, she will take a different path
• After exhausting all paths, Iva Jean can retire
from her latest job
• Question: When does Iva Jean get to retire?
work
home
Going to Work
• Being a practical person, Iva Jean only moves
systematically toward her goal.
• Moves only up (North) or to the right (East)
• Activity 3 – counting paths
Going to Work
• How many paths to an office 4 blocks away?
(4,0)
Only 1 path
(3,1)
4 paths
(2,2)
6 paths
(1,3)
4 paths
(0,4)
Only 1 path
Paths to Work
1
1
1
1
1
5
1
4
10
1
3
6
10
1
2
3
4
5
1
1
1
1
1
1
1
1
1
Paths to Work - Observations
• If the office is at (3,2), then is how many
blocks from home?
• (3,2) is 5 blocks from home
• The number of paths to (3,2) is: 10
• In terms of Pascal’s Triangle:
• The number of paths to (3,2) is: Pas(5,2)
• Notice that this is the same as Pas(5,3)
• Why is this all true?
Closer look at (3,2)
• Let E=East and N=North
• Think of paths as combos of E’s and N’s
• How many E’s and how many N’s in a path to
(3,2)?
• 3 E’s and 2 N’s
• (# of paths) = (# of words with 3 E’s and 2 N’s)
• EEENN, EENNE, ENNEE, NNEEE, EENEN, ENENE,
NENEE, ENEEN, NEENE, NEEEN
• How do we more easily compute this?
Closer look at (3,2)
• Every path to (3,2) has length 5
• Every path to (3,2) is a word consisting of 5
letters
• Not just any word of 5 letters
• 5 letter words with exactly 3 E’s and 2 N’s
• Think about placing the 2N’s into the 5 spots for
letters (3 E’s, 2 N’s)
• This is 5C2 = 5!/(2!3!)
Counting Paths
•
•
•
•
•
•
•
# paths to (3,2) is 5C2
By symmetry of paths, same as # paths to (2,3)
# paths to (2,3) is 5C3
Confirms 5C2 = 5C3
But, # paths is also Pas(5,2)
# of paths to (n,k) is (n+k)Ck = Pas(n+k,k)
Entries of Pascal’s Triangle are the binomial
coefficients!
• Do we already know this? (a+b)n+k
Summing Up
• First, how long until Iva Jean can retire?
• # of paths to (8,8) is Pas(16,8) = 16C8
• 16C8 = 16!/(8!8!) = 12,870 days ≈ 35 years
• Counting of block divisions of rectangles &
Counting of paths both lead to same structure
• Pascal’s Triangle
Pascal Patterns
1
+
+ +
+ + +
2
4
8
Pascal Patterns
An interesting pattern,
but any relationship to
either of our problems?
-
+
- + -
0
0
0
A Finer Counting
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
A Finer Counting
+
-
+
-
+
-
# of blocks
in Rectangle
1
2
3
4
5
6
Rectangle of
length 1
1
0
0
0
0
0
Rectangle of
length 2
1
1
0
0
0
0
Rectangle of
length 3
1
2
1
0
0
0
Rectangle of
length 4
1
3
3
1
0
0
Rectangle of
length 5
1
4
6
4
1
0
Rectangle of
length 6
1
5
10
10
5
1
The # of divisions into even # of blocks equals the # of divisions into odd# of blocks!
Pascal Patterns
0
-
+
- + -
0
0
0
• How do we express this pattern in terms of the triangle entries?
• That is, use Pas(n,k).
• Pas(n,0)-Pas(n,1)+Pas(n,2)- ... +(-1)kPas(n,k)+ ... +(-1)nPas(n,n)=0
Pascal Patterns
Pascal Patterns
Pascal Patterns
Pas(4,2) = 6 = 3+2+1
= Pas(3,1)+Pas(2,1)+Pas(1,1)
= Pas(3,2)+Pas(2,1)+Pas(1,0)
Pascal Patterns
Pas(8,3) = 56 = 35+15+5+1
= Pas(7,3)+Pas(6,2)+Pas(5,1)+Pas(4,0)
= Pas(7,4)+Pas(6,4)+Pas(5,4)+Pas(4,4)
= Pas(8,5)
Notice, in either formula, need to be
decreasing something!
Pascal Patterns
Pas(10,6) = 210 = 126+56+21+6+1
= Pas(9,5)+Pas(8,5)+Pas(7,5)+Pas(6,5)+Pas(5,5)
= Pas(9,4)+Pas(8,3)+Pas(7,2)+Pas(6,1)+Pas(5,0)
= Pas(10,4)
Pascal Patterns
Pas(n,k) = Pas(n-1,k-1)+Pas(n-2,k-1)+Pas(n-3,k-1)+...+Pas(k-1,k-1)
= Pas(n-1,n-k)+Pas(n-2,n-k-1)+Pas(n-2,n-k-2)+...+Pas(n-k-1,0)
= Pas(n,n-k)
Hockey Stick Pattern Formula
Pascal Patterns
10*6*35 = 2100 = 5*20*21
Pas(5,3)*Pas(6,5)*Pas(7,4) = Pas(5,4)*Pas(6,3)*Pas(7,5)
7*56*36 = 14112 = 21*8*84
Pas(7,1)*Pas(8,3)*Pas(9,2) = Pas(7,2)*Pas(8,1)*Pas(9,3)
Pascal Patterns
Pas(n,k)*Pas(n+1,k+2)*Pas(n+2,k+1) = Pas(n,k+1)*Pas(n+1,k)*Pas(n+2,k+2)
Star of David Pattern
Also tells us that the product of all six
entries around Pas(n+1,k+1) is a
Perfect Square!
And, if you take the pattern to the edge,
you get Perfect Cubes!
1*10*6 + 4*1*15 + 5 = 125 = 53
Part II – Geometric and Algebraic
Patterns
Golden Ratio
A Rose by any other name...
•
•
•
•
•
Golden Section
Golden Mean
Divine Proportion
Divine Section
Golden Number
Golden Ratio
•
•
•
•
•
•
Studied for thousands of years
Mathematicians
Artists
Biologists
Physicists
Musicians
What is the Golden Ratio?
Two quantities are in the golden ratio if their
ratio is the same as the ratio of their sum to the
larger quantity.
The common ratio is
What is the Golden Ratio?
This implies that the golden ratio is a fixed
constant, like π.
Can we compute it?
Solve it!
Algebraic Implications
The reciprocal of phi is one less than phi.
Algebraic Implications
What number is one more than phi?
Algebraic Implications
Let’s play with the recursive nature:
Can we do it again?
Have far can this go?
Algebraic Implications
Continued Fraction Expansion
Algebraic Implications
Convergents of the continued fraction
What do you notice?
Algebraic Implications
Will
Fibonacci
return?
Algebraic Implications
Try these! Compute the numbers
How do these relate to
the Golden Ratio?
Algebraic Implications
Prove that the continued square root
(infinite surd) also holds:
Trigonometric Implications
How would you get this one?!
When you see the number 5,
what shape do you think of?
Trigonometric Implications
Compute the
lengths of the
segments L and M.
Trigonometric Implications
A
HINT:
Consider the center
triangle, ABC.
Also, consider the
smaller (similar)
triangle, BCD that is
indicated.
You figure it out!
D
B
C
Trigonometric Implications
A
α=36
HINT:
Consider the center
triangle, ABC.
Also, consider the
smaller (similar)
triangle, BCD that is
indicated.
1
D
1
β/2
L-1
β=72
B
1
C
Trigonometric Implications
A
α=36 °
ABC and BCD are similar triangles.
1
So,
D
1
β/2
L-1
β=72 °
B
1
C
Trigonometric Implications
Trigonometric Implications
Now, how do we get:
π/5
cos(π/5) = (|L|/2)/1
Golden Rectangle –
Building the Golden Ratio
Start with a square;
side length 1
Golden Rectangle –
Building the Golden Ratio
Bisect the square.
Golden Rectangle –
Building the Golden Ratio
Draw the diagonal.
How long is the diagonal?
Golden Rectangle –
Building the Golden Ratio
Swing the diagonal
down along the base.
How long is the extended
base?
Golden Rectangle –
Building the Golden Ratio
What is the
ratio of the
length to width
of the
rectangle?
Golden Rectangle –
Who Cares?
Golden Rectangle –
Who Cares?
8.280
Ratio=1.6159
0.1% difference
From Golden Ratio
13.380
Golden Rectangle – Another
Construction
2
3
1
1
Rectangle Ratios:
1:1
2:1
3:2
5:3
8:5
Where did we see these?
Convergents of
continued fraction
5
Golden Spiral
Golden Spiral
Golden Spiral
Back to Fibonacci
We saw that the ratios of consecutive Fibonacci numbers
approach the golden ratio.
Why?!
Back to Fibonacci
This is a statement about limits.
Proof?
Back to Fibonacci
Back to Fibonacci
Back to Fibonacci
Back to Fibonacci
So, the Golden Ratio is the limit of Fibonacci ratios.
Can the Golden Ratio tell us anything about the
Fibonacci numbers??
Binet’s Formula
Plotting
Plotting
Pascal’s Triangle
Pascal’s Triangle
1
1
2
3
5
8
Pascal’s Triangle & the Number e?
1
1
2
9
96
2500
162,000
26,471,025
Pascal’s Triangle & the Number e?
1; 1; 2; 9; 96; 2500; 162,000; 26,471,025
Pascal’s Triangle & the Number e?
1; 1; 2; 9; 96; 2500; 162,000; 26,471,025
Do you see the patterns?
Pascal’s Triangle & the Number e?
1; 1; 2; 9; 96; 2500; 162,000; 26,471,025
Pi in Pascal’s Triangle
•
•
•
•
What is special about these numbers?
Triangular numbers
Sum of consecutive counting numbers
1+2+…+n = n(n+1)/2 = n+1C2
Pi in Pascal’s Triangle
• Similarly, we can add consecutive triangular numbers
• Tetrahedral numbers
Pi in Pascal’s Triangle