A Tour of the Catalan Numbers

This presentation explores five counting problems whose solutions are the Catalan numbers. Diagrams in the slides will draw connections between all of these apparently unrelated problems.

1. they’re everywhere…
*
Catalan Numbers
and their many combinatorics applications
*
A TOUR OF THE

2. What are the Catalan numbers?
a sequence of natural numbers
that shows up as the solution to lots of counting problems
1, 1, 2, 5, 14, 42, 132, 429, …
see a pattern?
it’s ok, I don’t
either…

3. What are the Catalan numbers?
the recursive pattern:
(this will make much more sense when we look at some example problems)
C0=1
Cn+1=
n
X
i=0
CiCn!i
and
e.g.
C4=C0C3+C1C2+C2C1+C3C0

4. Problem 1: Parentheses
the problem:
# ways to add parentheses to a product of n+1 letters so
that the order of operations is changed?
n=2
order of ops should be explicit: (abc) => ((ab)c)
an example: ((ab)c) (a(bc))
n=3
(((ab)c) d)
((a(bc)) d)
((ab) (cd))
(a ((bc)d))
(a (b(cd)))
Catalan .
recursion:
C2=2
C3=5
C2C0
C1C1
C0C2
+
+
split the n+1 letters into
two, nonzero length
sections. now you have
two smaller problems that
you know how to solve.

5. Problem 2: Full Rooted Binary Trees
the problem:# full rooted binary trees with n+1 leaves?
binary tree where each vertex has either 0 or 2 leaves
an example:
n=2
C2=2
n=3
Catalan .
recursion:
C2C0
C3=5
C1C1
C0C2
+
+
choose how many leaves
will be to the right and left
of the root vertex. now
make all full trees with
that # leaves.

6. Problem 2: Full Rooted Binary Trees
n=3
relation to .
parentheses:
(the trees are just
flipped upside-down,
and the edges are
longer for visual effect)
a b c d
(ab)
((ab)c)
(((ab)c)d)
a b c d
((a(bc))d)
(bc)
(a(bc))
a b c d
((ab)(cd))
a b c d
(a((bc)d))
a b c d
(a(b(cd)))

7. Problem 3: Polygon Triangulation
the problem:
# ways to draw diagonals in a n+2 sided polygon to make
n triangles?
an example:
n=2
n=3
Catalan .
recursion:
C2=2
relation to .
parentheses:
a
b c
d a
b c
da
b c
da
b c
d a
b c
d
(((ab)c)d) ((a(bc))d) ((ab)(cd)) (a((bc)d)) (a(b(cd)))
full explanation
tbd (b/c over
counting is
complicated)

8. Example 4: Tiled Step Diagrams
the problem:
# ways to “tile” (divide) a step diagram with side length n
into n rectangles?
an example:
n=2
n=3
Catalan .
recursion:
C2=2
relation to .
parentheses:
ab
bc
cd
ab
bc
cd
ab
bc
cd
ab
bc
cd
ab
bc
cd
(((ab)c)d)((a(bc))d) ((ab)(cd)) (a((bc)d))(a(b(cd)))
choose the largest rectangle you can fit. now you have
smaller step diagrams leftover that you know how to tile.

9. Example 5: NE Lattice Paths
the problem:
# north-east lattice paths from (0,0) to (n,n) that don’t
cross y=x line?
an example:
n=2
n=3
Catalan .
recursion:
C2=2
choose point (i,i) where the path will first touch
y=x line. now you have smaller path problems.
relation to .
parentheses:
north = letter | east = “(“
add “)” every time an added
letter completes a product
(((ab)c)d) ((a(bc))d) ((ab)(cd)) (a((bc)d))(a(b(cd)))