Next, we're going to study parameters of combinatorial classes of labelled

objects. And again, we're going to extend the same

basic methods that we used for counting in classes of labelled objects but to

study parameters. So we extend the basic definitions as we

did before. We're talking about labelled classes that

are sets of labelled objects that have a size function, but now they also may have

an associated parameter. And we define the exponential bivariate

generating function associated with a label class.

And it's the same power series some overall objects in the class, z to the

size of the object, u to the cost of the object divided by the size of the object

factorial. And we do that because the labeling

introduces so many possibilities. we have the usual fundamental identity if

you are summing over all objects you can group them according to the ones that are

of size N and cos k and get a double sum with the familiar enumeration.

and we use the same terminology, you know, z marks the size, u marks the

parameter. we can extend it to multivariate

generating functions, because we could have an arbitrary number of markers.

and if want to know the number of objects of size N with value k and we have the

exponential bivariate generating function then the number of objects of size N with

value k is equal to N factorial times the coefficient of z to the N and u to the k,

in the bivariate generating function. And as usual, with the symbolic method,

we specify the class, and at the same time, characterize the exponential

bivariate generating function. And so this is the transfer theorem, so

and I'll go through them very quickly, because they're the same as before.

union when we construct a class by taking disjoint copies of objects from two

classes. The OGF that we get is the sum of the

associated OGFs. Labeled product where we take pairs of

copies one from A one from B and relabel them in all consistent ways as we have to

for labeled classes, then we get the product.

sequence it extends the product operation in the generating function as 1 over 1

minus always have before. And again, construction immediately gives

the BGF equation as it did for enumeration.

and again, this extends immediately to mark multiple parameters.

so just a simple example how many different letters are there in a 3-word?

so in 3-word of length 1 they all have just one different letter and of length 2

there is 3 of them that have a one letter and there is six of them that have two

letters. of length 3, there is 3 that have one

letter, 111, 222, 333. six of them that have three letters, all

the permutations are 1, 2, 3 and the rest have two letters.

so and those have accumulated an average cost computed as usual.

So let's look at the use of exponential generating functions to solve this one.

So we have our class of all M-words. Our size is the number of letters in the

word. Our parameter is the number of different

letters in the word. so we have the exponential bivariate

generating function defined in the natural way.

so what does our construction look like? so, the construction for M-words is

sequence of sets of letters, but what we want to do is mark the sets that are

non-empty. the empty ones we, we won't mark and that

way we'll get the number of different letters.

So it's a sequence of sets, but the non-empty ones are marked.

so that immediately translates to this exponential bivariate generating function

equation. empty translates to one, u to u non-empty

set e to the z minus 1 and then sequence of length M, that's all of that to the

Mth power. [COUGH] so from that equation we can

evaluate that u equals 1 and get, you know, e to zM.

and we can differentiate with respect to u and evaluate it 1 and we get this

slightly more complicated expression. but when we divide the two, we get the

familiar result the average number of M words in a random average number of

different letters in a random M word of length N is N times 1 minus 1 minus 1

over M to the Nth. so, they're mostly going to be different

as N gets large. all the letter are going to be there.

[COUGH] and so, that's to be expected. And that checks with what we observed on

the previous page. so here, here is another example, we

could pick the frequency that we care about.

So, that's the number of different letters that appeared with any frequency.

what about the number of letters that appear k times?

so that's, we'll call that f k of w, the number of letters that appear k times.

So so that's going to be we're just going to mark the the ones that are not

equal to k, the ones that are equal to k. and the ones that aren't equal to k, we

won't mark. and so that gives us this simple EBGF

equation. and again, evaluate at 1 we get back our

number of M-words but if we differentiate with respect to u and evaluate at 1

essentially, we, you know, we show that the average number of letters that appear

k times is n times n choose k. and this is a familiar occupancy

distribution, which is what we'd expect. Again, just showing a simple

probabilistic derivation using the symbolic method for M-words.

So what about this, which I used as a motivating example early on?

How many permutations of N elements have k cycles?

so this is all the permutations of one one, two, three, four elements written in

cycle notation. and we can write out the distributions.

so for example, the number of permutations of three elements, where the

one cycle, there's just there are two of them, the two on the bottom.

the number with three cycles, there's just one, that's the one at the top and

the other three have two cycles. And similarly, we get this distribution

6-11, 6-1 for permutation of four elements.

And we can compute accumulated costs and the average 1.5, 1.8333, 2.0833.

That's an average number of cycles in the permutation of one, two, three, and four

elements. This is again, easily analyzed with

symbolic method unlabelled objects using exponential bivariate generating

functions. All we do is label the cycles.

Permutation is a set of cycle so we label the cycles mark the cycles would you.

so the generating function is e to the u log of 1 over 1 minus z.

that's log of 1 over 1 minus z is for cycles, and u is the mark and then set is

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

so to enumerate, evaluate that at z equals 1.

so the coefficient of z to the N in that is 1, multiply that by N factorial is N

factorial permutations. to compute the accumulated cost of the

number of cycles, we differentiate that with respect to u and then evaluate at 1.

So differentiate this with respect to u and then evaluate at 1.

and, you might need to practice your differentiate partial differentiation.

if you want, write this as an x log and you'll see that that result 1 over 1

minus c log of 1 over 1 minus c results. and then, therefore, the average number

of cycles in a random permutation is the ratio of the coefficients of those two

multiplied by N factorial. And that's exactly the harmonic numbers,

so the checks with what we observed the number of cycles of a random permutation

1, 2, 3, 4 is 1.5, 1.833, and 2.033 . So straightforward with the symbolic

method of marking the parameter value with the second variable u.

And again, we can go and computer the, the [COUGH] the standard deviation.

It's a square root of log N, so that 1 is even concentrated.