Or you can do the sum, and substitute p and k in there again and get back to p of

zu. Okay, so that's enumeration.

And again, this math over here is not really needed except to check your

understanding of what's going on. Now let's look at the cumulative cost.

the way that we compute averages when using generating functions is take the

total cost in the objects of size n and divide that by the number of objects of

size n. That's the average.

that's a little bit different calculation than working with probabilities but since

we have this powerful mechanism for counting, I am forgetting counting

results, it's natural to do it and we can see from the ordinary bjf how this works.

So we're interested in the total cost in objects to size in.

So, again, that's for all values of k, we multiply, the number of objects, the

size, and the cost k, by k, that gives the cost for all of those objects, then

we sum over all values of k, we'll just call that, q sub n.

what's that value in terms of the Generating Function?

Well what we do is we differentiate with respect to u, that's the marker variable

for the cost and then evaluate it, z equals 1 and u equals 1.

So that's the partial with respect to u of the ordinary bi-variate generating

function. A value at it u equals 1 just from the

definition that's the sum on all objects, cost times z to number of objects and

again if you collect all the objects of a given size n.

That's, exactly the same as q sub n z to the n.

So it's the coefficient of z to the n in the partial with respect to u of the OBGF

evaluated at z equals 1. or you can look at this representation on

the right of the generating function. when we, sorry this one at the top.

If you differentiate with respect to u, it brings down a k.

So that you get k, p and k. and that's the familiar way to think of

the total cost. but in terms of the, bivariate generating

function, it's a simple partial derivative and then evaluate at 1.

So that gives us what we need to calculate the mean cost of objects of

size n. we take the coefficient of z to the n, in

the partial with respect to u, of the OBGF.

Evaluate at u equals 1. And divide by coefficient of z to the n

in the OBGF evaluated at u equals 1. and that's in many cases, a simple

calculation. And again, that's the average, which

maybe you're more familiar in the form over here, kp and k over, over pn and we

can calculate then the variance in the same way.

definition of the variance is the sum on k, k minus the means squared times the

probability in, in terms of the ordinary bi-variate generating function.

it's not hard to check but that's the second partial with respect to u

evaluated at z equals 1. n subtract of at the mean, subtract of

the mean squared just as with normal probability calculations.

So that's a overview of calculating moments from an ordinary bi-variate

generating function. just using partial derivatives with

respect to the variable that marks the cost and then evaluating at that variable

equals 1. And we'll look at an example next.

So this is our bit strings example for what's the uh,[COUGH] number of zero bits

in a ran, a random binary bit string. we talked in the last section about our

construction In the OBGF equation 1 over 1 minus z times plus u.

So now we'll start with this equation and calculate the average number of 0 bits in

a bit stream. And again we know the answer to this it's

going to be half. but this will illustrate the calculation

and we'll use the very same straight forward method for more difficult

problems. so how many binary bit strings are there?

Well we evaluate at u equals 1. So that's 1 over 1 minus 2z, and then

take the coefficient of z to the n. Now that's 2 to the n, so that's as

expected. to do the cumulated cost, the total

number of zero bits in all bitstrings of length n, we need to compute the partial

with respect to u of the OBGF. So to compute the partial with respect to

u, it's 1 over 1 minus z minus z u. all that's relevant is the minus z u, so

it's that to the 1 minus z minus z u to the minus 1 power.

so it's minus that squared and then uh,[COUGH] times the minus z.

The two minuses cancel, so the partial, with respect to u of that, is over here

on the right, z over 1 minus z minus z squared.

and to calculate the accumulated cost, we just evaluate that, at u equals 1.

So if u equals 1 that's z minus z, 1 minus 2z squared.

So we want for the accumulated cost, the coefficient of z to the n, and z over 1

minus 2z squared. and that's an elementary calculation.

from s, power series that, that it's n times 2 to the n minus 1.

And so now the average is just divide those 2.

and that's n over 2 as expected. so it's just computing the partial with

respect to u, which you know, once you've practiced a few times and remembered the

definitions, it's not so difficult a calculation at all, and it's certainly

one that can be done automatically nowadays.

so we're not going to compute the variance because there's an easier way to

do it that we'll talk about in just a second.

[COUGH] Okay now I mentioned the idea of horizontal, and vertical generating

functions that go with bi-variate generating functions, and so now, I

want to take a look at moment calculation using these methods.

so, let's look at the moment calculations in terms of the horizontal, ordinary

generating function. So that's a generating function that

gives the cost for an object of a given size.

So what we do is we take the coefficient of z to the n, in the bi-variate

generating function, and we'll call that little p sub n of u.

It's a generating function for the cost and all the objects of size n.

and it's just the sum over all objects that are of size n, u to the cost of that

object. and again that cheat sheet over here in

the terms of, of p and k that's that's a sum on kp and k, u to k.

So it's the generating function for cost. and so that's only got one variable, and

since we're interested in knowing the number of objects of size n and the

average number of zero[UNKNOWN] an object of size n, we can use that generating

function directly to get the answer that we want.

So the first numeration if you evaluate that, u equals 1, you get the number of

objects of size n. so that's just evaluating the UV 1 that's

summing the for all values of k the number objects of size n cause k, that's

equal to the number of objects of size n. So this paying use the useful thing both

the numeration and for accumulated cost. If you just differentiate the function

and evaluate it at 1. Then at some kpnk, which is your

accumulated cost, qn. So if we know that pnu evaluated at 1 to

enumerate, differentiate evaluate at 1 to get the accumulated cost, and just divide

those 2 to get the mean. and even simpler calculation usually.

And then the calculation for the variance just involves the second derivative.

And again, that's easy to check from the definition, of the variance.

So this method, using horizontal ordinary generating functions, is the one that we

use most often, to calculate average values and other moments of parameters.