Today we're going to talk about combinatorial parameters and multivariate generating functions. this was a way using basically the same formal methods to get much more information about the combinatorial structures that we're studying. again we're still working with this symbolic method where we have a automatic method for getting from a specification to a generating function equation. And then later we're going to talk about use of complex asymptotics to get asymptotic estimate for the result, the kind of results that we want. But now we're going to focus on getting to the generating function equation. so let's just talk about the basic principles of combinatorial parameters. Up until now, we have really just been counting things but sometimes we want to know properties of the structures. Like we know that when the permutations consists of sets of cycles. We want, might want to know how many cycles we're likely to see in a random permutation on average. Or how many leaves are there in a random tree? Or, how many parts in a random composition, or in a partition? Or how many subsets are there in a set partition? Or, average number of times that each letter appears in a random M-word? these are all natural questions that we want to know good answers to in practice. And in part 1 of the course, we talked about all kinds of applications where we studied questions like this in some detail. average root degree of a random tree is another one. Now, there's one problem with this point of view is that sometimes it's easy to get average case results like this, but they're a little bit unsatisfying. And a famous example of that is an algorithm called separate chaining hashing. We'll look at in a little more detail later on. But basically it randomly assigns n keys to m lists. And you want to know the average length of a list? it's n over m. now but that's a trivial result. But but it's not that useful because it doesn't say anything about the length of a particular list. for example all the keys could be on one list, which would be something that we wouldn't want for performance. So, we want to know a little bit more than the average. And really, the techniques that we're going to talk about today in many cases, can extend to find the full distribution of the combinatorial parameter. so, for example, the probability that the value is k for all values of k. And with the distribution you can compute the average, but you can also compute other moments of the distribution that help tell us how likely it is that the thing has a certain value. and we can also compute extremal values like Well, the first, you could bound the probability that the length deviates significantly from the average, and that's classic in probability. Or we could study, like, the average length of the longest list or something like that. There's plenty of practical compromises to it. to get some kind of estimate that we can apply usefully in practice. so for this lecture what we're going to do is look at the basic symbolic methods to help us get generating function equations for parameters. And these in concert with the analytic techniques that we'll learn later, I'll often can get information about the full distribution of many of these parameters. Or about extremal values. But really, mostly we're going to interested in average and standard deviation and I'll talk about that in just a minute. So instead of talking about the average number of cycles, we're going to say how many permutations of n have k cycles. How many trees with n leave with n nodes, have k leaves? How many compositions have k parts? So now we have two variables, the number of objects and the value of the parameter. and these are natural questions, just rephrased using n and k. And so, those are the way, that is the way that we will be looking at our problems, studying combinatorial parameters in this lecture. so given that, then lets re visit our definition of what is a combinatorial class. So a combinatorial class is a set of combinatorial objects in and associated size function, what is what we said before. But now we're going to say, it may have an associated parameter, that's part of the definition of the class. Every objects, got a size and its got a parameter value. And then, given that, then we can write a bivariate generating function, a generating function with two variables. first we'll talk about ordinary bivariate generating functions just as we did before. and that's simply for every object in the class. We take the first variable z, and raise it to the power of the size of the object. And we take the second variable u, and raise it to the power of the cost of the object. That's a formal power series of two variables. And we're going to use the same kinds of arguments and manipulation on these two variable power series, that we used on the single varied power series before. But they carry the information that we can use to extract moments, and other information, about the values of parameters as you'll see. Again, we've got a fundamental identity, that again, is elementary. if you sum over all objects in the class z to the size u to the cost, what you can do is collect there's the term for every object. And you can collect the terms that have the same size, and the same cost. And write that coefficient ank, the number of objects the size n cost k, some on k some on n. that's an elementary identity. all of those things there has to be a term for all of those things in the ordinary bivariate generating function. And that's really collecting terms really just as before. We say that the variable z marks the size and the variable u marks the parameter. And actually you could add more variables and there's the discussion of multivariate generating functions in the text. And again, from the elementary identity you have the basic answer to the question, how many objects of size n with value k are there? That's the coefficient of z to the n, u to the k in the ordinary bivariate generating function. and again, as I just mentioned you could add arbitrary number of markers and have multivariate generating functions. I'm not going to discuss that in lecture, but it's covered in the book. So that's the basic definitions. And again, with the symbolic method we can have transfer theorems, symbolic transfer theorems that give us equations that the generating function must satisfy directly from the specification. And actually it's the same transfers pretty much that we discussed before. so let's start with a very simple and familiar example. binary strings. so when we introduce the symbolic method, we talked about enumerating binary strings. Now we're interested in some characteristic of binary strings. So they're 2 to the n of binary strings with n bits. But now, say we want to know how many n bit binary strings have k 0 bits? So that's a parameter on binary strings. And, so for example the 2 bit binary strings the [COUGH] the number that have 0, 0 bits, there's just one, the 1, 1. The number that have 1, 0 bits, there's two of them, 0, 1 and 1, 0. And the number that have 2, 0 bits, there's just one. Similarly, for 3, there's just 1 that has no 0 bits. The 1 1 1, and another one that has 3 0 bits 0 0 0, and so forth. And you recognize these coefficients, these are the binomial coefficients. And we know simple combinatorial argument really from the definition of binary. binomial coefficients the number of binary strings with k 0 bits is n choose k. We're just using this as an example to illustrate the formal mechanisms that we'll use the very same mechanisms for more difficult problems. so now since we have two variables our ordinary bivariate generating function has two variables and that's the result. And I'll show the two different ways to get that result. That's with the OBGF is. And actually we often consider these things as two dimensional arrays. So this is n going down and k going across. And so for two-bit binary strings there's 1 2 1. That's the distribution for the number of strings that have k 0 bits. and so forth So those are the familiar binomial, Pascal's Triangle binomial coefficients. in terms of the generating function one way to think about it is to write the, is to evaluate one of the sums. so if we evaluate the sum and choose ku to the k, we get 1 plus u to the n. So that then 1 plus u to the n is the coefficient of z to the n in a generating function. and that's called the horizontal ordinary generating function for for this problem. Coefficient of z to the n, and what it does is it gives the distribution of the number of k bits in n bit strings. 1 plus u to the n is a generating function for the number of k bits in n bit strings. There's one with 0, there's, this is for 7. There's one that has 0 1 bits, that's all ones. There's one with 7 1 bits, that's all 0 and so forth. That's the distribution. We call that the horizontal generating function. And sometimes, in fact many times what we'll do after finding the ordinary bivariate generating function is extract coefficients in this way to do the analyses, and we'll see examples of that. Or we can go the other way and evaluate the sum on z. So switch order of summation, evaluate the sum on z. some on the upper index and choose k sum on n, z to the n, it's z to the k over 1 minus z to the k plus 1. So the elementary generating function identity. So if you look at that function, which we called, the vertical OGF. as a generating function where you use the variable, the coefficient of u to the k is z to the k over 1 to the k plus 1. and so that's another way to analyze this generating function. So it gives for a fixed k it'll give the number of strings with k bits as n increases. so there's 126 9 bit strings with 5 bits and so forth. So now either evaluating either one of those sums maybe the horizontal one's the easiest or most familiar one. If you sum 1 plus u to the nz to the n. well that's just summing the quantity z times 1 plus u to the nth power over all n. So it's just 1 minus that quan, 1 over 1 minus that quantity. that's how we evaluate the ordinary bivariate generating function for a binomial coefficient. So for many of the problems we study we'll be looking at these various different ways to look at the ordinary bivariate generating function. but people are familiar with binomial coefficients so this is a good table to refer to, to check your understanding of this terminology. So, now let's look at the symbolic method for ordinary binary generating functions. it's the same setup as we've used before in lecture 1 for just regular single bivariate generating functions. If we've got value and we have their ordinary binary generating functions. z marks size, u marks your parameter value. Then if we do an operation like this joint union the same operation that we talked about before. Then ordinary bivariate generating function just translates to the sum. we'll look at the proof, it's an elementary proof just as before. Cartesian product translates to the product of the generating functions, again just as before. sequence translates to 1 over 1 minus, and again that follows from product just as before. So the same constructions, these are the same constructions immediately give us expressions on the ordinary generating function. Now what we do with those expressions is a bit more complicated. but the generating function equation part of the problem is very much as before. [COUGH] So immediately we get the the ordinary bivariate generating function equation. and now this also, if we wanted to include other variables then we could also expand this transfer theorem to hold for generating functions that have multiple marked parameters. [COUGH] Okay, so and these are the proofs of the correspondences. and there's no need to go into these in much detail because they're very similar to the ones that we did for single variant generating functions. and it's simply a matter of rearranging terms according to the definition. if we've got an object c in a plus b then either it's in a or it's in b. So we can split out the terms for those in a and for those in b and that's It's the proof of the, transfer theorem. for Cartesian product we have, since there's pairs of objects, we have a double sum and then we can uh,[COUGH]. Those sums are independent, so we can rearrange terms to simply get the product again just as before. And for sequence, sequence of length k is a to the k so the generating function is azu to the k just applying the product rule k times, or a sequence of any length. It's where actually for any subset of the integers you can just ex, expand the, the previous two rules to get an expansion like that. and for sequence of all integers, just 1 over 1 minus, just as before. So all those correspondences are, are immediate but we don't need to look at the sums anymore, because we'll just use the transfer theorems, which are natural extensions of what we've done before. So here's the, an example of using the symbolic method to derive that ordinary bivariate generating function for 0 bits and bit strings. and it's the, the same setup that we've used many times except now we add the parameter. So, class is the class of all binary strings, our size is the number of bits in the string, our parameters the number of 0 bits in the string. So, our ordinary binary generating function on the two variables is the sum for every object b, z with the size of the u to the number zeros in b. Our elementary identity says, that, we can collect terms, that have size n and cost k and that's, well, that'd be n k of those. all from, this is all elementary from the definitions. So our construction now is [COUGH] the same as before except that, what we're going to do is, put a variable u for every 0 bit. So, before, we had sequence of 0 bits and 1 bits, now we have sequence of marked 0 bits and 1 bits. We marked the 0 bits, but not the 1 bits and that's it. Now, the transfer theorum immediately translates that to this ordinary bivariate generating function equation uz ero transl-, uz 0 translates to uz, and z 1 translates to z, so we have a sequence operation applied to a class whose generating function is z times 1 plus u and then a sequence transfer says it's 1 over 1 minus that. So that's an immediate derivation of the ordinary bi, bivariate generating function for this class. and again we can, in the case, in this case, with binomial coefficients we can go ahead and expand and find, calculate the coefficients b and k which is exactly n choose k. so, in this calculation, what we do is we look for the coefficient of z sub n in bzu, thinking of u as a constant. That's 1 over 1 minus z to the 1 plus u. That expands to sum of 1 plus u to the nz to the n. So the coefficient is z to the n is 1 plus u to the n. And then we want coefficient of u to the k in that and that's n choose k. or you could do it the other way around and find the vertical generating function first. the point for this lecture is the equation that defines the generating function is immediate. and that's the basic idea behind using the symbolic method to study uh,[COUGH], combinatorial parameters. so those are the basics. Now we'll look at some real examples. [BLANK_AUDIO]
