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]

Â