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.