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]