0:04

as an introduction to the use of the symbolic method to describe combinatorial

Â classes while of the same time getting a generating function equations for the

Â generating functions of those classes. we'll look at trees and strings which,

Â provide rich set of examples as the way. from the elementary to some of the most

Â challenging combinatorial problems that have been studied.

Â so the classic example of the symbolic method is trees.

Â So how many trees are in there with N nodes?

Â where a tree is described recursively as a tree.

Â These are ordered, rooted trees. So it's a node connected to a sequence of

Â trees. and so these are the small values,

Â there's five different trees five nodes. And these two trees are different because

Â the order is significant and, and so forth.

Â So these are the familiar catalan numbers.

Â and with a symbolic method we can immediately drive the generating function

Â for the catalan numbers. so here's how it goes.

Â So we, we define the class of all trees to be G and then the construction using

Â the basic operations, we say a tree is a node in a sequence of trees.

Â it's as simple as that and just using the transfer theorem from the construction to

Â the generating function that we just described.

Â That immediately says that the generating function has to satisfy the equation z

Â for the node over 1 minus G of z for the sequence of trees.

Â G of z equals z times z over 1 minus G of z.

Â in solving that G of z minus G of z squared equals z, so that's an equation

Â that the generating function must satisfy that we get immediately from the

Â combinatorial construction direct transfer.

Â now we can solve this one in particular using the quadratic equation and in

Â classic analysis, the next steps are to use the binomial theorem to expand that

Â which is based extracting the coefficients.

Â and then with some a little bit of algebra, we can get down to the result

Â that G of N equals 1 over 4 minus 2, 2N choose N.

Â and then we can use classic analysis Stirling's approximation with again,

Â quite a few calculations to finally get down to the result that the number of

Â trees is asymptotic to 4 to the N minus 1 over square root of pi N.

Â And again, these types of calculations are what we covered in analytic

Â combinatorics part 1, if you're not familiar with them.

Â If you are familiar with them, you know that there's a fair amount of calculation

Â involved here. and again, what we're going to learn to

Â do in the second part of this course is to use complex analysis in this case

Â singularity analysis to immediately extract the asymptotic result.

Â so that's what we're going to talk about later.

Â for this lecture we're going to look at lot's of examples where we just stop at

Â the generating function equation. So that's our goal is to use the symbolic

Â method to derive generating function equations.

Â that's what we're going to be talking about for the next couple of lectures and

Â then we're going to how do we get the asymptotic results out?

Â now a very standard paradigm for the symbolic method that really helps to

Â explain, or helps you to understand its power, is this idea of just, we use

Â fundamental constructs to define things that are quite simple and intuitive.

Â It almost seems too simple even trees, that's an extremely simple construction

Â that I guess is down to the result that we want.

Â Sometimes, they're very trivial or elementary, but at least we can check

Â that and confirm our intuition that they indeed work.

Â We'll see plenty of examples of that but then we can compound the constructs and

Â immediately build up more complicated kinds of structures.

Â there's lots of possibilities. The set of combinatorial constructions

Â really is a, is a language that has unlimited possibilities.

Â and it turns out that even with a simple one we describe, we can get lots of

Â classic combinatorial objects that have been described that have been studied in

Â great detail. We can easily describe them with a

Â symbolic method and get equations that the generating functions satisfy.

Â what these constructs do is kind of expose the underlying structure in some

Â way and then reflect that information in the generating function equation.

Â but a lot of times we're just exploring one path to a known result for again the

Â natural combinatorial logics, a lot of them that we're going to look at today.

Â but the main point is that we can study variations that where we try other

Â possibilities we have restrictions on things, and so forth.

Â And this is what comes up and practical applications, and there's an unlimited

Â number of possibilities. But the structure that we learn from the

Â fundamental and compound constructs just follows right through.

Â and, and we get results that really we couldn't even consider approaching

Â otherwise. and that's a very standard paradigm that

Â we'll see in application after application for the symbolic method and

Â for analytic combinatorics. It's a calculus for the study of

Â quantitative properties of large combinatorial structures.

Â Calculus means that we have unlimited possibilities, once we understand the

Â basic operations. so just in the context of trees lets look

Â at a few variations, just a very few variations on a theme.

Â so we said a tree is a node in a sequence of trees another variation is to say well

Â each node can have either zero or two children that's called a binary tree.

Â and again immediately you can write down a construct that's a variant on the basic

Â construct. this says a binary tree's a node and a

Â sequence of 0 or 2 binary trees, and you can construct things like that.

Â and that immediately gives the generating function equation, T of z equals z times

Â 1 plus T of z squared, or we can do a variation where we consider multiple node

Â types. for example, suppose we wanted to

Â distinguish the nodes that have 0 children from the nodes that have two

Â children in a binary tree. this is important in computer

Â applications where binary trees are used explicitly as data structures to support

Â fundamental search algorithms and operations.

Â so in that case we're working, start working with, different, atomic elements.

Â to build up a combinatorial class the internal node is the one that we consider

Â to be of size 1. So, its generating function is z,

Â external nodes we consider it to be of size 0, so their generating function is z

Â to the 0 or 1. then we use a construction with both

Â types of nodes so a binary tree is either an external node, node with zero

Â children, or a binary tree with an internal node and a binary tree, that's a

Â node with two children. That with those definitions for what the

Â atoms are, again from the basic transfer theorems immediately transfers to again

Â an OGF equation, T of z is 1 plus z, T of z squared.

Â or we could enumerate by external nodes and switch the sizes and then it that

Â case we get T of z equals z plus T of z squared.

Â and it turns out actually, that all of these generating functions are related

Â and related to the catalan numbers. and there's interesting things that we

Â can learn combinatorial, but combinatorial from this manipulation but

Â for the present the point is that however we want to specify it it's very easy to

Â get the generating function that enumerates all these different types of

Â trees. so there's many more variations that have

Â been studied, and many of these are talked about in the book.

Â and the trees are so fundamental, there's other ways to look at them.

Â so gambler's ruin paths or context-free languages, or triangulations, and all

Â sorts of other combinatorial structures or equivalent to tree structures.

Â so these basic kinds of operations are going to lead to generating function

Â equations that help us enumerate a very, very broad variety of combinatorial

Â structures. so these are just some examples order

Â tree, we just talked about or binary tree or there's a thing called the

Â unary-binary tree, where you allow nodes to have 0, 1, or 2 children.

Â or you could have ternary or four-way trees or whatever else you wanted.

Â there's a thing called, bracketings which is a famous problem of Schroeder.

Â where we allow, we disallow unary nodes. It's the opposite of unary-binary a node

Â has to have either zero or greater than two children.

Â and that's related to the number of ways you can parenthesize N variables.

Â and again each one of these equations immediately translates to a generating

Â function equation and they're all different.

Â And in fact, you can have arbitrary restrictions on what the how many

Â children a node can have. and for any set then you can get a

Â generating function equation that describes the trees that have those kinds

Â of restrictions. there's plenty, there's applications for

Â all of these sorts of things and for not many more.

Â so that's an illustration of the idea that we can start with a fundamental

Â construct and get to variations that help us study a broad variety of things that

Â are structurally similar. Another example of that is strength,

Â again we start with a very basic fundamental construct, say the class of

Â all binary strengths. Well a binary string is either empty or

Â its a 0 or 1 bit followed by a binary string that immediately gives an OGF

Â equation B of z equals 1 plus 2 of z, B of z and that now immediately leads to

Â the the solution B of z equals 1 over 1 minus 2z of the number of binary strings

Â is 2 to the N. But then we can have all kinds of

Â variations on that theme. So one is say the the class of binary

Â strings that don't have a sequence of P or more zeroes.

Â well that string with no sequence of P or more zeroes is a string of zeros of

Â length less than P and followed by it's either that, or it's that followed by a 1

Â followed by another string with no zero to the P, just generalizing that same

Â argument. And that immediately gives a OGF equation

Â that the generating function for these strings, must satisfy.

Â And then we can find z to be in an equation, we know the number of such

Â strings. And there's lots of applications where

Â people want to know things of this sort. and this extends to being able to

Â disallow any pattern whatsoever. it extends to describing the numerator

Â strings in regular languages or in unambiguous context free grammars and

Â many many other implication. And again start with the basic binary

Â string. there, actually there's two ways to write

Â down a construction for a binary string. You could also say it's just a sequence

Â of 0 and 1 bits. Either way, you get to the same

Â generating function and or you could say [UNKNOWN], so M different letters or the

Â example I did exclude strings of zeroes or exclude a particular pattern we talked

Â about that in detail in part 1, lecture A.

Â and again, regular images and context free images.

Â Again, starting with the most elementary construction.

Â But then using the operations in natural ways we can study a broad galaxy of our

Â combinatorial structures. [COUGH] That's introduction to the use of

Â symbolic method for basic structures trees and strings.

Â [BLANK_AUDIO]

Â