0:00

[BLANK_AUDIO]. So, many many different combinatorial

constructions have been defined. and we don't have time to go through all

of them. But, I'll do one more, called

substitution. So these are the ones that, we've

discussed so far, in this lecture, disjoint union, Cartesian product,

sequence, powerset and multiset and again everyone of these has immediate

translation to a generating function and there's many others that are, are

available and still being invented. so I, I just want to look at one more

example called substitution. so again we have A and B classes and you

have the generating functions. substitution is written with this

operation A open circle B in brackets. And what it says is, to replace each

object in an instance of A with an object from B.

And if you do that you get the, compound generating function, A of B of z.

so and the canonical example of that is called enumeration of 2-3 trees.

2-3 trees, are, an interesting combinatorial structure.

that actually have important practical applications in computer science.

again, data structures that are used to implement fast search.

and there are trees in which the distance from the root to the bottom is always the

same. and every node has exactly two or three

children. so there's only one 2-3 tree with four

external nodes but there's two with five external nodes.

It's gotta be a 2-node and a 3-node and the 3-node can be there in the left or

the right. There's also 2 with 6 external nodes.

You could have 2-3's or you could have 3-2's, and so forth.

So how many 2-3 trees are there within the nodes?

And with the substitution operation it's easy to write down a generating function

equation for these types of trees so that's the generating function equation

using substitution, together 2-3 tree what you do is you take each external

node and replace either with a 2-node or a 3-node.

Then with this distance from the root to the bottom is always the same, so that

gets struction as a way to construct all 2-3 trees and you want to pick up a

coefficient of z to the n of that to find out the number of 2-3 trees with n nodes.

but, the combinatorial construction immediately gives the, that OGF equation.

Now that's a more complicated kind of OGF equation than we've seen.

we can check that it, that it works. from the previous slide, here's the

leading term. of the generating function.

there's 1,2,3,4 there's 2 of 5 and 6, 3 of 7, and 4 of 8 and so forth, and if you

just plug in z squared plus z cubed and in collect terms then, you'll see that

you get 1,2, 1,3 ah[COUGH] One 4, 2 5's, 2 6's, 3 7's, and so forth.

so that's an interesting OGF equation that we get from substitution.

now coefficient asymptotics of this one is extremely difficult and we'll talk a

bit about it later. It actually has oscillations in the

leading term that's a reference for that, but we'll talk about it later.

so I'll just to finish up I want to give some quotes too.

It seems so natural to immediately get generating function equations from

combinatorial construction that but this approach definitely was controversial for

a while so this is a quote from 1968, not all that long ago.

where Berge said that really what combinatorials should be doing is is

confined to bijection. that's really what we want to know why,

why is that that the number of trees of n node is exactly the same as the number of

binary trees of the external nodes and so forth.

so property is understood better when one constructural bijection than when one

calculates the coefficients of a polynomial whose variables have no

particular meaning. And what he said was[LAUGH] the method of

generating functions, which has had devastating effects for a century, has

fallen into obsolesence for this reason. it's something about variables that have

no meaning, and devastating effects. I'm not quite sure how, what he meant.

but what Felipe came to understand despite this attitude, which was a

prevailing attitude in many circles, when he was a student, Felipe came to

understand in the 80s and 90s that generating functions really are the

central objects of the, of the theory of analytic connotorics.

They're not a mere artifact of solve recurrances as many people believe,

they're the central object. we can get generating functions from the

symbolic method and then we can use generating functions to get coefficient

asymptotics. so just want to finish with the overview

that I started with. that we use the symbolic method to get

generating functions and, and just want to put out that we get generating

function equations that vary widely in nature.

we have all these strange type, types of equations that arise when we use the

symbolic method and many more. So, it's not necessarily going to be a

challenge to get coefficient asymptotics and products out of all these types of

equations. that's for part two of the course.

so that's just a look at another construction within the symbolic method.

And a comment on the various types of generating functions that we might

derive.

[BLANK_AUDIO]