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]
