0:03

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.

9:50

In fact, this distribution is another well-known one, it's known as Stirling

numbers of the first kind. the Stirling cycle numbers, so these are

what we observe for one, two, three four the horizontal exponential generating

function for this. It's u times u plus 1 times u plus 2 and

so forth. and in the vertical one is 1 over k

factorial log and 1 over 1 minus z to the k.

and the one we derived, the exponential bivariate generator function 1 over 1

minus z u. Then there's arguments for getting both

of these and extracting coefficients and so forth.

quite a bit is known about the Stirling numbers of the first kind as well.

what about the number of cycles of a given length?

How many cycles of length r can we expect to find in a random permutation?

it's just a matter of naming a parameter, and then marking that parameter with the

cycles of length r, we mark with u. The ones that are not of length r, we

won't mark. and so, then we get an exponential

generating function immediately from the symbolic method, that is e to the log 1

over 1 minus z, but we subtract off the z to the r over r term and then add a

marked one. so that works out to be e to the u minus

1, z to the r over r over 1 minus z. Of course, if you evaluate that at u

equals 1 then we just get 1 over 1 minus z as before.

if we differentiate with respect to u and evaluate at z minus 1, it pulls out z to

the r over r. If we take the coefficient of z to the N

and divide and then evaluate at 1, and then divide, then we get 1 over r.

The average number of r-cycles in a random permutation is 1 over r.

and that's an, an interesting result. There's one, one cycle there's half a two

cycle, third of a three cycle, so and most of the cycles are, are going to be

small in a random permeation. okay, here's a different problem.

How many ways are there to partition a set of size n?

so we've got two elements, either we can partition into two subsets or leave them

in one, there's two different ways. for three, there's five different ways.

three different subsets all in the same subset or two subsets.

And for four, there's 15 different ways. and actually the we'll, we'll prove the

number, but we're also interested in knowing how many are there that partition

into k different subsets. so for three as I just said there's one

that has just one subset, there's one that has three subsets and the rest of

them have two. For four, it's one, seven, six, one and

we can compute the cumulative costs and the average and maybe you recognize these

numbers but let's use the symbolic method to study it for now.

so we have the class of all set partitions our s, our size is the size of

the set and our parameter is the number of subsets in the partition and then

there's our exponential bivariate generating function.

so, the construction is the set of sets, except we're going to mark the subsets.

simple as that. so it's a set of non-empty subsets that

are marked. so that's the set of non-empty subsets is

e to the z minus 1, they're marked with the u.

A set of those is e to that power. Evaluate that at u equals 1 and the,

enumerate the exponential generating function to enumerate those is e to the e

to the z minus 1. And the cumulative cost is derivative

with respect to u of that which it multiplies it by e to the z minus 1.

and average of subsets and random of set partition is the ratio that now these are

getting to be complex calculations and we'll need the uh,complex some tactics,

that we're going to study in this second half of this course to actually find out

that number. but maybe you recognize the numbers.

actually this is the Stirling numbers of the second kind.

this exponential bivariate generating function.

We had an ordinary bivariate, bivariate generating function for the same number.

the horizontal is the Bell polynomials, but now we divide by N factorial.

[COUGH] and vertical is found by extracting coefficients of z to the N.

and that's essentially the derivation that we gave.

but again, there's another whole set of identities involved with understanding.

the Stirling numbers of the second kind and here they are coming up in completely

different application with exponential generating functions.

Finally, there's the combinatorial object labelled combinatorial object called a

mapping. and we studied the derivation of

generating a function equations for enumerations of mapping.

The functions from the integers 1 to N onto itself.

We can write mappings as a digraph where every element has a link to now whatever

element it maps to. And we're interested in questions like

how many connected components are there? How many nodes are on cycles?

How many on trees and so forth? And again, if you want to see motivating

applications of this, look in part 1 of the course.

and these, these is a summary of what we did in the last lecture starting with

Cayley trees. A Caylee trees a root connected to a set

of trees, which gives the EGF equation C equals ze to the C.

mapping components are cycles of trees which is log of 1 over 1 minus C of z.

And the set of mappings is a set of components, so it's e to that power,

which leaves the 1 over 1 minus C. So those are the EGFs, and in the context

of this lecture, the point is, we can use these same constructions to get

generating functions for mapping parameters.

so number of components, mapping is the set of cycles that we're just going to

remark the cycle, the cycles of trees and that gives us the number of components.

So that's it was, it's e to the u log 1 over 1 minus C which is 1 over 1 minus C

to the u. So that's an EGF equation to describe the

number of components in a map. or if we want the number of trees, then

we take a set of cycle and then we mark the trees.

and that gives a completely different equation although this symbolic

manipulations are very simple. and that was 1 over 1 minus uCfz for the

number of nodes on cycles in a mapping are the number of trees.

So, define the moments and coefficients, then we're going to have to work with

trying to find the derivatives with respect to u or extract coefficients.

and you remember, for enumeration we we [COUGH], we needed advanced techniques

and we're certainly going to need advanced techniques from complex

asymptotics. Although, actually, these turn out to be

handled with powerful general theorems that give the answers almost immediately.

but that's a subject for second half of the course.

I think at this point quote Philippe that we can stop supplying examples now,

because with the tools that we have, the combinatorial construction, we could

provide examples at, at liberty. Because but we're, we're going to stop

doing that, because to get, to actually extract the coefficients, involves lots

of, lots of calculations with the techniques that we have.

but when we get to complex analyses we're going to be able to eliminate really a

lot of those calculations and simplify them greatly.

but that's a topic for second half of the course.

So that's an introduction to parameters in labelled classes.