Trees and Strings

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]

解析组合数学

审阅

教学方

Robert Sedgewick

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。