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.

Â