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.

Â