[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]