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. 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.
