1 00:00:00,012 --> 00:00:06,641 So now I want to finish up this lecture by giving indication of how these kinds 2 00:00:06,641 --> 00:00:12,700 of problems can be solved with analytic combinatorics in this, in the symbolic 3 00:00:12,700 --> 00:00:16,848 method. essentially those derivations in a sense 4 00:00:16,848 --> 00:00:21,812 were a, a little bit the hard way, and there's an easier way. 5 00:00:21,812 --> 00:00:28,010 Now we'll develop this fully in part two but it's, it's worthwhile to take a look 6 00:00:28,010 --> 00:00:33,835 at typical derivation using analytic combinatorics because it's actually not 7 00:00:33,835 --> 00:00:38,097 that much more difficult. And, actually, the idea is to use 8 00:00:38,097 --> 00:00:43,747 bivariate generating functions. that's really the way to analyze combinatorial 9 00:00:43,747 --> 00:00:47,672 parameters. so the idea is, for combinatorial class, 10 00:00:47,672 --> 00:00:53,412 we have not just the size function, but we also have an associated parameter that 11 00:00:53,412 --> 00:00:58,852 has a cost and we want to analyze the cost associated with the size. We're 12 00:00:58,852 --> 00:01:04,002 looking for the average number of cycles in all permutations of size N and so 13 00:01:04,002 --> 00:01:07,047 forth. So, the way that we do that, say for 14 00:01:07,047 --> 00:01:12,571 unlabeled objects, is to just take another variable, u and define the 15 00:01:12,571 --> 00:01:18,927 bivariate generating function, z and u, where z is for size and u is for cost. 16 00:01:18,927 --> 00:01:25,475 So for every object we take z to the size of that object and u to the cost of that 17 00:01:25,475 --> 00:01:30,145 object. So that's what we work with for labeled 18 00:01:30,145 --> 00:01:35,800 classes we divide by the size factorial but it's the same idea. 19 00:01:35,800 --> 00:01:40,202 So that's the form that we're going to work with for permutations. 20 00:01:40,202 --> 00:01:45,206 Now the idea is that those constructions that we gave are going to work just as 21 00:01:45,206 --> 00:01:50,474 well to give us formulas that these bivariate generating functions have to 22 00:01:50,474 --> 00:01:56,341 satisfy and not only that. The bivariate generating function really does carry 23 00:01:56,341 --> 00:02:00,672 full information about the association between size and cost. 24 00:02:00,672 --> 00:02:06,637 and again, it's pretty much as easy to compute as the as the CGF and we'll look 25 00:02:06,637 --> 00:02:11,784 at those computations next. and not only that using this approach 26 00:02:11,784 --> 00:02:18,031 with analytic combinatorics, it's often a case that we can get full distribution of 27 00:02:18,031 --> 00:02:23,536 the asymptotics or the full distribution by knowing and generating a formula that 28 00:02:23,536 --> 00:02:27,066 the bivariate generating function has to satisfy. 29 00:02:27,066 --> 00:02:32,894 So it's extension of the symbolic method beyond just counting to also take into 30 00:02:32,894 --> 00:02:37,294 account cost of parameters in combinatorial structures. 31 00:02:37,294 --> 00:02:42,743 So what are the, the basic calculations? So we start with a a bivariate generating 32 00:02:42,743 --> 00:02:48,419 function. This is exponential for labelled classes like permutations 33 00:02:48,419 --> 00:02:52,390 because that's all the examples I've done so far today. 34 00:02:52,390 --> 00:02:58,403 so if you want to go back to the way that maybe you are used to thinking of things 35 00:02:58,403 --> 00:03:04,019 and, and we had in our tables actually the number of elements of size N with 36 00:03:04,019 --> 00:03:10,694 parameter value k then that [COUGH] have the fundamental identity, which just 37 00:03:10,694 --> 00:03:15,447 extends what we did for single varied generating functions. 38 00:03:15,447 --> 00:03:22,204 if you're summing in all combinatorial objects you can gather them together by 39 00:03:22,204 --> 00:03:28,173 size and by cost and then the number with [COUGH] size N and cost k, that's the 40 00:03:28,173 --> 00:03:35,657 coefficient of z^N/N u^k because everyone of those objects will contribute one to 41 00:03:35,657 --> 00:03:41,761 the sum, you gather them together, you have A Nk objects that have that sum. 42 00:03:41,761 --> 00:03:47,305 And so that identity is implicit when we're trying to understand the 43 00:03:47,305 --> 00:03:54,231 combinatorics of it we work with the representation where we have a term and a 44 00:03:54,231 --> 00:04:00,961 sum for every object but when we want to do some counting we use the elementary 45 00:04:00,961 --> 00:04:04,703 identity to get us the results that we need. 46 00:04:04,703 --> 00:04:10,749 So for example the, as I just said, the number of objects of size N with value k 47 00:04:10,749 --> 00:04:14,632 we can get from a bivariate generating function. 48 00:04:14,632 --> 00:04:20,922 It's the coefficient of z^N, coefficient of u^k divided multiplied by N for the 49 00:04:20,922 --> 00:04:25,340 label. so but what's interesting is what's the 50 00:04:25,340 --> 00:04:28,892 average value of a parameter for a permutation. 51 00:04:28,892 --> 00:04:35,802 It's the coefficient of z^N and the partial derivative of the bivariate 52 00:04:35,802 --> 00:04:40,659 generating function with respect to u evaluate at u=1. 53 00:04:40,659 --> 00:04:47,315 it seems like maybe kind of a strange operation to perform but the calculation 54 00:04:47,315 --> 00:04:52,272 is, is really simple. So if you take the partial of A(z,u) with 55 00:04:52,272 --> 00:05:00,639 respect to u you get ku^k-1. so now if you evaluate that at u=1 then 56 00:05:00,639 --> 00:05:06,914 that u^k-1 goes away, and if, now if you look at that sum, 57 00:05:06,914 --> 00:05:14,182 what's the coefficient of z^N in that? it's the sum of k A and k. 58 00:05:14,182 --> 00:05:17,885 and then, again, the trick, the divide by N. 59 00:05:18,997 --> 00:05:25,142 So it's the sum of k, the probability that it's k over sum of k, the 60 00:05:25,142 --> 00:05:30,247 probability that it's k which is exactly the average. 61 00:05:30,247 --> 00:05:37,517 So just knowing that one little really trivial calculation means that we can go 62 00:05:37,517 --> 00:05:43,457 ahead and [COUGH] use our constructions to tell us about the bivariate generating 63 00:05:43,457 --> 00:05:48,881 function and just do that one, differentiate with respect to u and 64 00:05:48,881 --> 00:05:55,197 evaluate at u=1. so this is the construction that we did 65 00:05:55,197 --> 00:06:01,153 earlier on say for average number of cycles and, and this is the same slide as 66 00:06:01,153 --> 00:06:05,928 above so I won't spend too much time talking about it. 67 00:06:05,928 --> 00:06:11,859 so we apply our construction and then simplify the sum to get down to the 68 00:06:11,859 --> 00:06:17,693 harmonic numbers. so let's do it with bivariate generating 69 00:06:17,693 --> 00:06:24,469 functions. So bivariate generating function, it's z to the size over size 70 00:06:25,541 --> 00:06:28,089 factorial u to the cost. So now our same construction which has 71 00:06:28,089 --> 00:06:31,412 for [COUGH] for cycles, for every permutation, we construct a bunch of 72 00:06:31,412 --> 00:06:54,457 other ones and p of those have the same number of cycles and one of them has one 73 00:06:54,457 --> 00:06:54,762 more cycle. So that's what this equation says, that 74 00:06:54,762 --> 00:06:55,937 those, those permutations of size p+1 one of them has one more cycle, that's u to 75 00:06:55,937 --> 00:07:01,417 the cycles of p+1 and p of them have the same number of cycles, that's p u to the 76 00:07:01,417 --> 00:07:04,492 cycles of p. So rearranging the terms and the sum 77 00:07:04,492 --> 00:07:10,212 according to this construction implies that identity on the bivariate generating 78 00:07:10,212 --> 00:07:15,504 function. And that one is not so difficult to 79 00:07:15,504 --> 00:07:24,735 [COUGH] simplify so z^|p|+1/ (|p|+1), that means we should differentiate with 80 00:07:24,735 --> 00:07:32,918 respect to z, and if we do that then we get two simple sums that we can easily 81 00:07:32,918 --> 00:07:37,773 simplify. the first one is just zB (z u), uh,, and 82 00:07:37,773 --> 00:07:44,783 [COUGH]· I mean, sorry, uB (z u), and the second one has is like the derivative 83 00:07:44,783 --> 00:07:48,944 with an extra factor of z and you can check that. 84 00:07:48,944 --> 00:07:55,846 It's a very simple calculation. And now we can solve for derivative of u 85 00:07:55,846 --> 00:08:02,585 with respect to z and we have B sub z (z u) = u/1-z, B(z u),. 86 00:08:02,585 --> 00:08:08,101 That's a differential equation in z that we can just solve. 87 00:08:08,101 --> 00:08:14,294 And it's 1/(1-z)^u. And it's a little shocking at first that 88 00:08:14,294 --> 00:08:21,049 there should be such a simple solution but once you think of u as a constant and 89 00:08:21,049 --> 00:08:26,906 just work with the z it's not it's not so amazing a calculation. 90 00:08:26,906 --> 00:08:33,402 and that's an explicit formula for the bivariate generating function. 91 00:08:33,402 --> 00:08:38,324 And what do we want from that formula? what we want is the average value of our 92 00:08:38,324 --> 00:08:41,346 parameter. How do we get the average value of that 93 00:08:41,346 --> 00:08:46,453 parameter? For any bivariate generating function, all we do is differentiate with 94 00:08:46,453 --> 00:08:52,093 respect to u and evaluate at u=1. Differentiate with, that with respect to 95 00:08:52,093 --> 00:08:56,277 u, evaluate at u=1 you get 1/1-z, log 1/1-z. 96 00:08:56,277 --> 00:09:02,723 that and the coefficient of z^N in that is your average, which is the harmonic 97 00:09:02,723 --> 00:09:06,603 numbers. So the same kind of construction leads us 98 00:09:06,603 --> 00:09:10,069 to our result. But what really makes bivariate 99 00:09:10,069 --> 00:09:16,277 generating functions the method of choice is, is that we can actually get rid of 100 00:09:16,277 --> 00:09:21,937 this sort of construction stuff and really use this symbolic method and, and 101 00:09:21,937 --> 00:09:27,797 again we'll talk about many examples of this later on but I want to show it for 102 00:09:27,797 --> 00:09:31,347 this one. so the idea is to just carry the cost 103 00:09:31,347 --> 00:09:36,237 along with the combinatorial constructions and the transfer theorems 104 00:09:36,237 --> 00:09:43,689 and everything else follow right through for a bivariate [COUGH] and with, without 105 00:09:43,689 --> 00:09:49,110 much difficulty at all. so this symbolic method will take us 106 00:09:49,110 --> 00:09:55,171 right to where we need to get. so this says, a permutation is a set of 107 00:09:55,171 --> 00:10:03,378 cycles of z and the variable u marks the number of cycles and, and that's it. 108 00:10:03,378 --> 00:10:13,828 so that immediately leads to the through transfer theorem which is the same cycle 109 00:10:13,828 --> 00:10:22,417 is log 1/1-z and set is e to the, immediately leads to e^u log 1/1-z. 110 00:10:22,417 --> 00:10:30,357 so simple combinatorial construction immediate transfer to BGF equation and 111 00:10:30,357 --> 00:10:35,077 there we are, no sums at all. and what do we want? We want to 112 00:10:35,077 --> 00:10:39,402 differentiate with respect to u, evaluate at u=1. 113 00:10:39,402 --> 00:10:46,687 and in this form, it's the same function, it's 1/1-z^u just written in exp log 114 00:10:46,687 --> 00:10:50,294 form. it's obvious that the derivative with 115 00:10:50,294 --> 00:10:57,032 respect to u is going to bring out a factor of log 1-z and then leave leave 116 00:10:57,032 --> 00:11:03,130 this term, evaluate u at u=1, it's just 1/1-z. so immediate from the transfer 117 00:11:03,130 --> 00:11:10,100 theorem to there and then immediate derivative evaluated at u=1 which 118 00:11:10,100 --> 00:11:15,879 immediately gives the harmonic numbers. So derivations of this simplicity 119 00:11:15,879 --> 00:11:22,152 replacing the ones we've been doing is really persuasive evidence or the 120 00:11:22,152 --> 00:11:28,436 persuasive bottom line that BGF's and the symbolic method are the method of choice 121 00:11:28,436 --> 00:11:34,348 in analyzing parameters. we're going to see many examples of that 122 00:11:34,348 --> 00:11:38,839 in part two. and so here's say another example. 123 00:11:38,839 --> 00:11:45,349 So we, you wanted to know the average number of cycles of size 1 that we did an 124 00:11:45,349 --> 00:11:52,446 exercise with 2 and r and so forth. So here's that derivation using symbolic 125 00:11:52,446 --> 00:11:56,540 method. So, a number of cycles of size r well, 126 00:11:56,540 --> 00:12:02,871 it's a set of cycles that are not of size r plus the cycles that are of size r 127 00:12:02,871 --> 00:12:09,781 marked with the cost variable u. That's it and so, by transfer theorem, 128 00:12:09,781 --> 00:12:16,797 that immediately gives log of 1-z with minus, with the 1 for r subtracted off 129 00:12:16,797 --> 00:12:23,788 and then added back on marked with u. so immediate from the transfer theorem to 130 00:12:23,788 --> 00:12:31,332 that BGF equation and then what's the value we're interested in? We want to 131 00:12:31,332 --> 00:12:38,415 differentiate with respect to u, evaluate at u=1 and that is immediate 132 00:12:38,415 --> 00:12:43,839 differentiate with respect to u brings out to the z^r/r, 133 00:12:43,839 --> 00:12:51,442 evaluate at u=1 just makes it e to the log 1/1-z and that's the generating 134 00:12:51,442 --> 00:12:58,827 function for the average number of cycles and what's the coefficient of z^N in 135 00:12:58,827 --> 00:13:02,852 that? It's 1/r as long as N is bigger or equal to r. 136 00:13:02,852 --> 00:13:11,137 So the working with the constructions in the way we did earlier is at the level of 137 00:13:11,137 --> 00:13:18,617 detail that analytic combinatorics can free us from and again, we'll see many 138 00:13:18,617 --> 00:13:26,687 more examples of working with parameters that allow us to use the symbolic method 139 00:13:26,687 --> 00:13:32,142 for bivariate generating functions in this way. 140 00:13:32,142 --> 00:13:35,725 [COUGH]. So that, that'll be mostly in part two. 141 00:13:35,725 --> 00:13:43,371 and just to to quickly finish up without going into much detail this parameter, 142 00:13:43,371 --> 00:13:49,599 the number of permutations with size N with k cycles it's, has got a long 143 00:13:49,599 --> 00:13:56,110 history and lot's of applications that we don't have the time to talk about in 144 00:13:56,110 --> 00:14:00,528 detail. so in, it's written, it's called Stirling 145 00:14:00,528 --> 00:14:05,823 numbers of the first kind and it's usually written nowadays in square 146 00:14:05,823 --> 00:14:11,283 brackets like that. So for permutations of size 3 there's two 147 00:14:11,283 --> 00:14:18,719 of them that have one cycle, three of them that have two cycles and one of them 148 00:14:18,719 --> 00:14:25,670 that has three cycles. And for 4, it goes 6, 11 6 and 1 and so 149 00:14:25,670 --> 00:14:30,552 forth. so what we just did was show that 150 00:14:30,552 --> 00:14:36,886 the [COUGH] if we just define the BGF for Stirling numbers of the first kind, we 151 00:14:36,886 --> 00:14:44,815 just showed that it's 1/(1-z)^u and you can use that form to develop all kinds of 152 00:14:44,815 --> 00:14:50,180 interesting ID, identities for the Stirling number. For example, the, the 153 00:14:50,180 --> 00:14:57,561 distribution of for a given N the number of cycles of size N [COUGH] is the 154 00:14:57,561 --> 00:15:05,581 coefficient of z^N/N, which if you, if you, if you use Taylor's theorem to 155 00:15:05,581 --> 00:15:12,572 expand this you get u*(u+1), (u+N-1) and so forth. 156 00:15:12,572 --> 00:15:18,178 so it, it's, if you take that polynomial as a polynomial in u the coefficients of 157 00:15:18,178 --> 00:15:24,253 that polynomial give you the Stirling numbers of the second time, second kind. 158 00:15:24,253 --> 00:15:29,835 and you can also come up with a way to compute them and get a recursive formula, 159 00:15:29,835 --> 00:15:35,978 like the basic formula for binomial coefficients and, and so forth and we'll 160 00:15:35,978 --> 00:15:43,134 come back to some more details about, about this in part two I just wanted to 161 00:15:43,134 --> 00:15:49,308 point out that this, this kind of structure in more detail has been studied 162 00:15:49,308 --> 00:15:55,192 a great deal. in fact, here's a a distribution with the 163 00:15:55,192 --> 00:16:03,772 with the scaling by N and actually one of results in analytic combinatorics we 164 00:16:03,772 --> 00:16:10,522 study try to learn about limiting distributions in situations like this and 165 00:16:10,522 --> 00:16:18,032 that actually, I can show that this distribution is normal in certain ranges. 166 00:16:18,032 --> 00:16:24,257 so that's the use of bivariate generating functions and introduction of an easier 167 00:16:24,257 --> 00:16:28,382 way to deal with analysis of parameters in permutations. 168 00:16:28,382 --> 00:16:33,882 so I just want to finish up with by pointing out a couple of exercises that 169 00:16:33,882 --> 00:16:38,607 people could do to test their understanding of the material that we've 170 00:16:38,607 --> 00:16:42,657 talked about so forth, so far. So the first one is this study 171 00:16:42,657 --> 00:16:46,864 arrangements. so an, an arrangement of N elements is a 172 00:16:46,864 --> 00:16:50,715 sequence formed by a subset of the elements. 173 00:16:50,715 --> 00:16:56,480 so that's a a permutation use element, each element once and only once. 174 00:16:56,480 --> 00:17:01,288 With arrangement, you could use some of them more often. 175 00:17:01,288 --> 00:17:07,789 and so the problem is to prove to study arrangements and to get some kind of 176 00:17:07,789 --> 00:17:13,772 combinatorial interpretation. and the, this next one tests two 177 00:17:13,772 --> 00:17:19,797 different concepts of that we've brought up and that's inversions and involutions. 178 00:17:19,797 --> 00:17:23,752 So find the average number of inversions in an involution. 179 00:17:23,752 --> 00:17:31,472 and there's no real reason to do that other than to test out the mathematics. 180 00:17:31,472 --> 00:17:39,952 and then this third problem gets at what is the cycle length distribution look 181 00:17:39,952 --> 00:17:48,052 like? so it, it actually turns out to be asymptotic to Poisson distribution. 182 00:17:48,052 --> 00:17:53,890 and from the generating functions you can, you can show that and that's an 183 00:17:53,890 --> 00:18:00,342 interesting problem to work through. so for the next lecture read the [COUGH] 184 00:18:00,342 --> 00:18:05,104 Chapter 7 uh,, in the text. again, it's kind of encyclopedic, so you 185 00:18:05,104 --> 00:18:11,610 might find yourself skipping through analysis of certain parameters but some 186 00:18:11,610 --> 00:18:17,422 of them have interesting applications. I think it's always a good idea to run 187 00:18:17,422 --> 00:18:22,232 some experiments to validate the mathematical results that we've developed 188 00:18:22,232 --> 00:18:27,025 and it's easy to generate random permutations so why not do it to just 189 00:18:27,025 --> 00:18:30,702 check that. say the average number of cycles or the 190 00:18:30,702 --> 00:18:36,261 average number of 1-cycles in a random permutation agree with the results 191 00:18:36,261 --> 00:18:41,334 predicted by, by our analysis. and even for distribution for that 192 00:18:41,334 --> 00:18:45,344 exercise where we're doing the distribution of cycle length takes more 193 00:18:45,344 --> 00:18:52,149 cycle, more [LAUGH] computer cycles to study cycles but it's worthwhile to run 194 00:18:52,149 --> 00:18:55,057 experiments to validate these things always. 195 00:18:55,057 --> 00:19:02,560 and, and again, it is used worthwhile to practice writing up solutions to 196 00:19:02,560 --> 00:19:06,611 exercises like this. so that's permutations.