0:03

As a poster child for the application of generating functions next we're going to

take a look at the Catalan numbers, which are a fundamental sequence of great

interest in combinatorics. one way to, there's many applications of

the Catalan numbers, and I'll give a few. So one of the earliest that people

thought about was, how many different ways are there to take a polygon with n+2

sides and draw lines from one vertex to another and make it all triangles?

So for example if you have a pentagon, you have all these different ways to

triangulate it well actually it's easy just draw from any vertex you draw to the

two opposite and in a five vertices you get five triangulations or if it's a

square you just get two but if you, if it's a hexagon, there's lots of

possibilities you can do three like that or you can do these N shapes and there's

lots of possibilities and actually turns out that the number of triangulations of

a hexagon is fourteen. so that's a number sequence that is

described by this recurrence relation, over here.

the in, in general if we draw and leave K.

we draw our diagnol and leave K vertices on one side, and N minus one minus K on

the other side, and there's one less because we draw the triangle, then you

can triangulate those anyway that you want and each one of them independently.

So it says thatt the number of triangulations has to satisfy that

reccurence relation, sum from zero to K less than N, T, K, T, N minus one, K,

plus an extra because there's always one way to triangulate the

the triangle. So that's a recurrence relation that

we're going to take a look at solving. but it applies in many other

applications. here's another application the so called,

gambler's ruin problem. So you're a gambler,

you start with zero dollars and you make $1 bets.

And if you win, the line goes up. There's just a graph of the amount of

money that you have. So in this case, there's two wins,

followed by a loss. Win, loss, win, loss, two wins and then a

bunch of losses. And the idea is the gambler will keep

going until having $0 makes a bet and loses and then the game's over.

And how many different A's so are there for, for, the for, for the gambler to do

that, I would say N, N wins in the sequence and a lot of b loses to and so,

and again, if you try out all the possibilities it turns out that, there's

only two possibilities, if there's two dollars you could win, lose, win, lose or

you can win 2 and then lose 3 and those are the only two possibilities.

And there's five different ways for three wins in fourteen for four wins.

And same sequence because it satisfies the same recurrence.

You can just set up the recurrence by the first time the gambler gets back to zero

if that happens after K wins. then independently you have a gambler's

ruin problem on K and then N minus 1K. And it follows the same recurrence.

U, here's another one binary tree structures.

So a binary tree is a root node that has connected to two binary trees, the tree

on the left and the tree on the right or it could be empty.

w-, that's called an external node. So how many different binary trees are

there with N nodes? And we'll look in much m-, in a lot of

detail at binary trees later one. So this f-,

Two different binary trees with two nodes so that is you got one of the root and

you could have a one node tree on the left or a one node tree on the right and

every node has to have two children and the ones at the bottom have two blank

children, those are called external nodes.

For three, there's five possibilities you have a node at the root and it could be

empty on the right with either one of these trees on the left or it could be

empty on the left with either one of these trees on the right or you could

have two trees of size one, one on either side.

so there's five possibilities for three nodes.

And similarly, there's fourteen possibilities for four nodes.

so, you could have empty on the left, and anyone of the three node trees empty on

the right. Anyone of the three node trees on the

left. Empty on the left, anyone of the three

node trees on the right. or you could have one on one side and two

on the other side in four possible ways. so again, same number sequence again,

satisfies the same recurrence. if you got k nodes on the left, you are

going to have n minus one minus k nodes on the right.

And you can try all possibilities on either side so it's got to satisfy the

recurrence, where you, T equals n is equal to the sum for all k up to n minus

one of Tk, Tn minus one minus k plus delta trying to make it true for zero,

Catalan numbers. here's another one.

How many trees with n nodes? A tree is a node connected to a forest of

trees. To any number of trees, so it's not

restricted to be just two. And again, we'll talk in detail later in

the course. about trees and binary trees.

but for now, I just want to point out all the possibilities.

and it satisfies these same recurrents. so Catalan numbers describe a lot of

combinatorial objects of interest. So how are we going to solve the Catalan

recurrence with generating functions? Well, we're going to use the formula.

we got the recurrence that holds for all N.

now we're going to, what's the next step? It's multiply by Z to the N and sum on N.

on the left hand side, that gives us T of z.

that's the generating function for the Catalan numbers.

On the right hand side we'll get a one for the delta term on the right.

and then we get some [INAUDIBLE] zero. Zero less than or equal to K less than N,

TKTN - 1. and that looks familiar, it is familiar.

that's we're going to work backwards from the

convolution derivation that we did before.

so, Now what we'll do is, first thing we'll

do is switch order of summation. so switching order summation means if

you're try for every value of K then the inner sum is just for N bigger than K.

now in that inner sum will change N to N plus K plus one.

Change n to n+k+1, n bigger than k, that's n bigger than or equal to k+1.

So that's the same as n bigger equal to zero.

And then the t sub n-1-k just becomes T sub N.

And then we have z^(n+k+1). And that gives us a way to split it into

independent sums by distributing the ks and the ns.

And then you can see immediately the one z comes out and then it's two copies of

the generating function t of z. so that's a backwards convolution that

shows us that the Catalan generating function has to satisfy this functional

equation. T of c equals one plus z times t of z

squared. So we're halfway there.

we've got a, an equation that the generating function has to satisfy.

Now I. Common sense rule for working with

generating functions that I want to point out, and again it's always worth while to

check your math with your computer, and that includes symbolic, calculations,

like this one, You know the initial values of T of Z, we

did the, we did the examples so we know that it starts out being one plus Z, plus

2Z squared plus 5Z cubed plus 14Z four. before we go any further we might want to

check that this equation that we have are really holds and you can do it in pencil

and paper or you can use a symbolic maths system and you could see that if you take

1 + z times 1 + z^2 and so forth I just took it out to four terms here the ones

that we know if we multiply them out it the you get 1 +z+2z z +2z^2 + 5z^3 + 4

and so forth. Now after a while the terms are no good

because we didn't take these terms far enough.

but still that gives confidence and actually you can boot strap this to get

more terms. But, it gives confidence that we've got

the right equation. so that's just checking your math with

the computer even when it's, symbolic. Alright so now what we need to do is to

extract coefficients to find an expression for the N-th Catalan number.

So that's the GF equation well it's an equation we know how to solve with the

quadratic formula. and so that's the solution with the

quadratic formula. just implying the eighth grade formula.

and then, we have to pick 1 plus or 1 minus and

It, it's going to be the minus. So just left out that one consideration.

and that you get from checking with the initial values.

so now how do we deal with that? We, we expand one over, square root of 1

- 4Z with, just use the binomial theorem. It's 1 - 4Z to the one-half power, so

it's the sum of one-half 2's and 4Z to the N.

and then this one part goes away. and so, and again, we can check that from

initial values. so that's a key step for this generating

function. We have a solution that uses the

quadratic formula. And then we have a [COUGH] an expansion

of a function that we know how to expand, know how to find coefficients.

so that tells us what T sub N is. it's minus a half.

One half choose N plus one minus four to the N plus one.

This extra Z is what gives to, leads the, the N plus one.

Now that is, it is okay, it is not totally satisfying because the one half

n+1 is may be not such familiar function in its way to manipulate this to get it

to be a little more familiar function and actually next time we will talk about

much better way to continue to manipulate it to get really a concise

representation. But let us just do a little more algebra

to get the. It's in more of a form that we can people

can. relate to so

This is the definition of the binomial coefficient, when the upper index.

for any binomial coefficient we just, it's

On the bottom is N plus one factorial. And on the top is N plus one terms, where

we subtract zero, one, two, all the way up to N.

so that's just the do, definition. And there's the - 1/2 and there's the - 4

to the N + 1. And so now what we're going to do is take

we have N plus one terms here and we've got n plus one force and we're going to

take a bunch of those if we'll take the n plus one minus 2's and multiply them in,

and one of them kills that and then the others you get one, three, five all the

way up to 2n minus one like that. so that's a slight trick but cleans it up

quite a bit and now if you have that then if you fill in the evens so two to the n

is two over one times four over two and so forth.

As now we have the odds and the evens and we have an n factorial so that's going to

immediately give us 2n factorial over n factorial times n factorial which is 2n

choose n. So that's a proof that the number of

binary trees in N nodes, number of general trees in N nodes, the number of

ways to triangulate an N plus 2-gon, and so forth.

The Catalan numbers is one over N plus one, times two N choose N, and that's one

of the most famous number sequences in combinatorics.

and we'll see in many cases we explicitly use data structures like trees in

practical algorithms and data structures. So we need to understand these properties

of them. and we're going to continue working with

the Catalan numbers in several other occasions later on in the course.