0:05

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.

Â 11:31

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]

Â