Transcript +1 - Western Illinois University

“Catalan Numbers and Pascal’s Triangle”
Jim Olsen and Allison McGann
Western Illinois University
http://www.wiu.edu/users/mfjro1/wiu/
IMACC
Robert Allerton Park, IL
March 27, 2010
Catalan Numbers are:
1, 1, 2, 5, 14, 42, 132, 429, 1430, …
Notation:
C1 = 1
C2 = 2
C3 = 5
C4 = 14
Also, C0 = 1
1
Pascal’s Triangle
1
1
1
1
2
3
1
3
1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
The
nth
r
entry in row r is   or r Cn
n
(n and r start with 0)
6
Example:   =20
 3
Catalan Numbers in Pascal’s Triangle
by subtraction
1
1
1
1
2
3
C1  2  1  1
1
1
3
1
C2  6  4  2
1 4 6 4 1
1 5 10 10 5 1 C3  20  15  5
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Characterization #18 of Pascal’s Triangle
The difference of the middle number in an even row
and its neighbor is a Catalan Number.
Catalan Numbers in Pascal’s Triangle
by division
1
1
1
C


2

1
1
1 1
2
1 2 1
1
1 3 3 1
C2   6  2
3
1 4 6 4 1
1
1 5 10 10 5 1
C3   20  5
1 6 15 20 15 6 1
4
7
21
35
35
21
7
1
Characterization #19 of Pascal’s Triangle
The middle number in an even row, divided by half
the row number plus 1, is a Catalan Number.
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
6  6
C3        20  15  5
 3  2
1  6 1
C3      20  5
4  3 4
2 6 10
C3     5
2 3 4
10
5
C3  C2
 2  5
4
2
C3  C0  C2  C1  C1  C2  C0
 1  2  1 1  2 1  5
Problems
Find the number of ways we can
order 2n numbers from a list
made up of n +1’s and n -1’s such
that the sum (from the beginning)
at any point is 0.
Example: n = 3
1, 1, 1, -1, -1, -1
1, 1, -1, -1, 1, -1
1, 1, -1, 1, -1, -1
1, -1, 1, 1, -1, -1
1, -1, 1, -1, 1, -1
5 ways  C3 = 5
n +1’s and n –1’s
Find the number of ways a rook in
the lower left corner of an (n+1)
by (n+1) chess board can get to
the upper right corner, without
ever crossing the diagonal.
Example: n = 3
5 ways  C3 = 5
Problems
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Problems
Find the number of ways to
triangulate an (n+2)-gon
Example: n = 3
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
5 ways  C3 = 5
Problems
Find the number of ways to put
n sets of parentheses in a list of
(n+1) letters (to indicate the n
multiplications).
Example: n = 3
(((ab)c)d)
((ab)(cd))
(((a(bc))d)
(a((bc)d))
(a(b(cd)))
5 ways  C3 = 5
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
n pair of
parentheses
Problems
The number of trivalent
rooted trees with n trivalent
vertices (it has n+1 branches).
n +1’s and n –1’s
Example: n = 3
Rook moves
n+1 by n+1 board
A
B
C
D
A
B
C
D
A
B
C
D
Triangulations
n+2 - gon
A
B
C
D
5 ways  C3 = 5
A
B
C
D
n pair of
parentheses
Trivalent trees
n+1 branches
Formulas
Problems
Difference
n +1’s and n –1’s
 2n   2n 
Cn     

n
n

1
  

Rook moves
Quotient
n+1 by n+1 board
1  2n 
Cn 
we will show the connections
 Now

n 1 n 
Triangulations
Product•Why are the formulas equivalent?
n
4•Why
i  2 are the problems equivalent?
n+2 - gon
Cn  
i  1 do the formulas solve the problems?
i 1 •Why
…But WHY?
Recursive
4n  2
Cn  Cn 1 First, a few easy ones.
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
n pair of
parentheses
Trivalent trees
n+1 branches
Formulas
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
Problems
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Left as an
exercise (in
simplifying
factorials).
Triangulations
n+2 - gon
n pair of
parentheses
Trivalent trees
n+1 branches
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
n +1’s and n –1’s
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n pair of
parentheses
n 1
Cn   Ci  Cn 1i
i 0
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
“obvious”
Trivalent trees
n+1 branches
Formulas
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
Problems
n +1’s and n –1’s
+1 corresponds
to a rook move
to the right.
–1 corresponds
to a rook move
up.
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
n pair of
parentheses
Trivalent trees
n+1 branches
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
n +1’s and n –1’s
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n pair of
parentheses
n 1
Cn   Ci  Cn 1i
i 0
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Trivalent trees
n+1 branches
Prove the Summation formula solves the
Triangulations of an n+2-gon Problem
n 1
Prove: Cn   Ci  Cn 1i is a formula for the
i 0
number of triangulations of an n+2-gon
Let C0  1
Proof by induction on n.
11
n=1:
C1   Ci  C11i  C0  C0  11  1
i 0
This is a formula for the number of
triangulations of a 3-gon, because there
is 1 triangulation of a triangle.
Induction Step
Inductive hypothesis:
h 1
Assume Ch   Ci  Ch 1i is a formula for the
i 0
number of triangulations of an h+2-gon, for
all h<k.
k 1
Prove Ck   Ci  Ck 1i is a formula for the
i 0
number of triangulations of a k+2-gon
Consider a k+2-gon.
Here are a couple of
triangulations.
…
Consider a k+2-gon.
Label two consecutive
vertices X and Y.
This leaves k additional
points. We label these
points P0, P1, P2,… Pk-1.
P2
Pi
P1
P0
X
Y
Every triangulation of the polygon will include
a triangle with the points X, Y, and Pi.
Every triangulation of
the polygon will include
Pi
a triangle with the points
X, Y, and Pi.
…
P2
P1
P0
X
To form an entire triangulation of the
polygon containing triangle XYPi, we
need to triangulate the points to the
right of the triangle, and triangulate
the points to the left of the triangle.
Y
We need to triangulate the
points to the right of the
P
i
triangle, and triangulate
the points to the left of the
triangle.
…
P2
The number of points to
the right and to the left is
X
Y
less than k+2, so we know how
many triangulations there are to the right and to
the left. We will multiply these, by the
fundamental counting principle.
In fact, the number of triangulations to right is Ci
and the number of triangulations to left is Ck-1-i
P1
P0
For example, k=6
Octagon, i=3
We need to triangulate the
5 points to the right of
triangle XYP3, and
triangulate the 4 points to
the left of the triangle.
(Only one triangulation on
each side is shown.)
Pi =P3
P2
P1
P0
X
Y
The number of triangulations to right is C3=5. The
number of triangulations to left is C2=2. So, there
are 25=10 triangulations which contain this
particular triangle (XYP3).
We let the point Pi go from P0 to Pk-1. We see that
The number of triangulations of a k+2-gon is
k 1
Ck   Ci  Ck 1i
…
i 0
P2
Pi
P1
P0
X
Y
Therefore, by the principle of strong induction,
n 1
Cn   Ci  Cn 1i
i 0
is a formula for the number of triangulations of an
n+2-gon. (The formula is valid for all natural numbers.)
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
n +1’s and n –1’s
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n pair of
parentheses
n 1
Cn   Ci  Cn 1i
i 0
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Trivalent trees
n+1 branches
Triangulation
Expression
ABCED
Tree
Triangulation
Expression
C
Tree
A
B
D
A
E
ABCED
B
C
D
E
Triangulation
Expression
C
Tree
A
B
D
A
E
AB(CD)E
B
C
D
E
Triangulation
Expression
C
Tree
A
B
D
A
E
A(B(CD))E
B
C
D
E
Triangulation
Expression
C
B
A
D
(B(CD))
A
Tree
E
(A(B(CD)))E
B
C
D
E
Triangulation
Expression
C
B
A
D
(B(CD))
E
A
(A(B(CD)))E)
Tree
((A(B(CD)))E)
B
C
D
E
Triangulation
Expression
C
B
A
D
(B(CD))
E
A
(A(B(CD)))E)
Tree
((A(B(CD)))E)
B
C
D
E
Triangulation
Expression
Tree
>> Second Example <<
ABCED
Triangulation
Expression
ABCED
Tree
Triangulation
Expression
C
Tree
A
B
D
A
E
ABCED
B
C
D
E
Triangulation
Expression
C
Tree
A
B
D
A
E
(AB)CDE
B
C
D
E
Triangulation
Expression
C
B
A
D
(AB)
A
Tree
E
(AB)C(DE)
B
C
D
E
Triangulation
Expression
C
A
D
(AB)
(DE)
B
A
Tree
E
((AB)C)(DE)
B
C
D
E
Triangulation
Expression
C
Tree
A
D
(AB)
(DE)
B
E
A
(((AB)C)(DE))
(((AB)C)(DE))
B
C
D
E
Triangulation
Expression
C
Tree
A
D
(AB)
(DE)
B
E
A
(((AB)C)(DE))
(((AB)C)(DE))
B
C
D
E
Formulas
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
Problems
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
See Handout
(Math Induction)
n pair of
parentheses
Trivalent trees
n+1 branches
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
See
n
4i  2
Cn  
Rook Moves Proofs
i 1 i  1
n +1’s and n –1’s
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n pair of
parentheses
n 1
Cn   Ci  Cn 1i
i 0
Handout
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Planted trivalent
Trees n branches
Formulas
Problems
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
See
n
4i  2
Cn  
Handout on the n
i 1 i  1
n +1’s and n –1’s
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n pair of
parentheses
n 1
Cn   Ci  Cn 1i
i 0
+1’s and n -1’s
problem
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Planted trivalent
Trees n branches
Formulas
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
For further
Investigation:
Problems
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Interesting proof (can
be of
n pair
found online). Involves
parentheses
building new triangulations
from old.
Trivalent trees
n+1 branches
Formulas
Difference
 2n   2n 
Cn     

n
n

1
  

Quotient
1  2n 
Cn 
 
n 1 n 
Product
n
4i  2
Cn  
i 1 i  1
Recursive
4n  2
Cn  Cn 1
n 1
Summation
n 1
Cn   Ci  Cn 1i
i 0
For further
Investigation:
Problems
n +1’s and n –1’s
Rook moves
n+1 by n+1 board
Triangulations
n+2 - gon
Pretty easy –
See Martin
Gardner article.
n pair of
parentheses
Trivalent trees
n+1 branches
References
• Mathematical Games: Catalan numbers: an integer sequence
that materializes in unexpected places. By Martin Gardner.
Scientific American. June 1976, Vol 234, No. 6. pp. 120-125.
• Wikipedia.com – Catalan Numbers
• Catalan Numbers with Applications. Book by Thomas Koshy.
Oxford Press. 2009. 422 pages.
• Enumerative Combinatorics (http://math.mit.edu/~rstan/ec/ )
two-volume book and website by Richard Stanley. Includes
66 combinatorial interpretations of Catalan numbers!
• The On-Line Encyclopedia of Integer Sequences (by AT&T) http://www.research.att.com/~njas/sequences/index.html
Type in 1, 2, 5, 14, 42
Thank You
Jim Olsen and Allison McGann
Western Illinois University
http://www.wiu.edu/users/mfjro1/wiu/
[email protected]