Alright, next, let's look at some other examples that we use the symbolic method for to get generating function equations. And we'll look at several of the examples that we considered in the first two lectures. And see that mero-, meromorphic asymptonics directly gets us to accurate asymptotic estimates of coefficients. So derangements that's one of our classic problems. Where we want to know the number of permutations of size n that have no singleton cycles. So, that's a familiar combinatorial construction. A derangement is a set of cycles where the length of all the cycles is greater than one. That immediately translates to this generating function or equation, e to the minus z over 1 minus z. That's a meromorphic function. It's the ratio of two analytic functions. So our basic procedure is going to apply. what's the singularity? There's only one. It's z equals 1. it's got a, a, a strange structure outside but as for negative z it gets large, but the singularity is that z equals 1. so then we can easily compute the residue the derivative of the denominator is minus 1, which cancels the minus. And the numerator valued at the singularity is just e to the minus 1. so then the meramorphic transfer theorem tells us that the coefficient is this e to the minus one over one in the exponential growth, is one to the n. So our asymptotic result is that the coefficient of z to the n, which n factorial coefficient z to the n, in that generating function is asymptotic to and factorial over e. [COUGH] and that comes immediately from the meromorphic transfer theorem. And this one also we can generalize. Well one thing first to notice is that these estimates are extremely accurate, even for small, and for n equals 5 we're within point 1. And that's because the in this case there's the Error term is simply to do with the numerics of the function. Other cases are singularities, but they're exponentially smaller. so let's look at the class of all permutations. with no cycles of length less then or equal to m or m's a perameter. so the again, the comonotorial construction through the symbolic method immedietly gives a generating function an equation that can be pretty complicated to try to find exact expressions for coefficiants in that equation. But the meromorphic transfer theorem immediately gives us the asymptotics just as before again, the, there's a pole at one and I'll show the since I have m, I don't have any plot. [LAUGH] and the residue is the same as before. evaluating the numerator at one is e to the minus h m. 1 plus 1 plus one third minus a e to minus a h and the derivative of the denominator is minus 1, which cancels the minus. So we get e to the minus hm. and again exactly the same argument, there's no exponential growth, so it approaches 1 over ehdm. So, whatever m is, you can approximate the number of permutations with no cycles of length less or equal to m by that simple formula, about 1 over e to the h m of em. Of all permutations have no cycles of length list in the recall of m. And that's a very accurate going to be accurate result. and lets look at the singularities of those. So that's the one I showed for no cycles of size 1. here's with node cycles of size 2. Still, there's just one singularity but the growth of the what goes on outside changes in interesting ways. And it's still only one singularity, and it's on the real line and it's, it's closer to the origin by Pringsheim's Theorem, so we know all this from the theorems. In terms of the calculation or we can all, the whole growth of this complicated thing, is even though it's a fantastic thing, looks like an integrated circuit or something. the whole growth is just determined by the value of that singularity that's closest to the origin. so that's that's derangements, and again, that's kind of a poster child for analytic combinatorics, because it's so easy to get to that asymptotic result. Apply the symbolic method apply the meromorphic transfer theorem, and you're there. well, that was the same for strings, and actually that's going to be the same for many, many of the combinatorial classes that we've considered. here's another one that we talked about. surjections. so these are the coupon collector sequences and so they're words of length n With the property that for some m, each of the fir-, first m letters appears at least once. So these are all the ones where for m equals 2 here's the one's for m equals 3, and here's the one's for m equals 4 in this case. So that's surjections. And that's one way to look at it, so how many surjections are there. We saw the comminitorial construction for surjections. A surjection is just a sequence of sets, that are, none of which are empty. And that immediately translates to the generating function equation. set that's not empty is z, z minus 1. Sequence is 1 over 1 minus. So that's equal to 1 over 2 minus e to the z. That's a meromorphic function, it's a ratio of two analytic functions. So what we care about is the poles. This one has a lot of poles. whenever z equals log 2 plus or minus 2 to the, 2 pi i. there's going to be a pole. the only one we care about is the one that's on the real line, closest to the origin. and we just go ahead and turn the crank, and apply the theorem to compute the residue. so differentiate the bottom you get minuses, you cancel g minus log 2 is just one half. so, the coefficient is going to be 1 over 2 log 2 in the exponential growth is going to be log 2 to the n. 1 over 2 log to the n plus 1. Again, immediately from the construction to the generating function, through the transfer theorem, to the asymptotic result. again the, these other poles might contribute something to the growth but it's exponentially small. And these are pretty far away. This is extremely accurate. Even for 3 it's accurate to three decimal places. and we can look at general versions of this like double surjec, surjections. So that's like Coupon collector sequences, where you want to have two of everything. so for sum m, each of the first m letters appears at least twice. and, and again, there's lo-, the applications for wanting to study these types of combinatorial objects. in terms of the analytic combinatorics is just generalizing the one that we just did. It's a sequence of sets where the sets are all two or more. translates to the generating function. So sets all two or more is e to the z minus z minus 1. Sequence is 1 over 1 minus that so we have this generating function for r of z. Again, that's meromorphic ratio of two analytic functions. What we care about is when the denominator is 0. this one's a little, getting to be a little more complicated in terms of the singularities but the keypoint is that there's only one on the real line. its closet to the origin. The others are going to be exponentially small. so we have to do a calculation to find the value where on the real line where e to the z equals z plus two and that turns out to be 1.14 in this case. And we go ahead and calculate the residue, which is just the derivative of that evaluated here and turns out to be just 1 over that plus 1. so again that little calculation immediately gives the asymptotic growth for a number of double serjections. Bing, bing, bing no matter how complicated the generating function gets, we go right through it to get the simple asymptotic result. and this one also generalizes so that's one, that's two. Now you can see the extra poles are getting their influence is getting weaker. well there's one of the imaginary axis that is getting more, and then that one turns into two, and these other ones that are out here are very tiny. and then, turns into three, and starts to look a little bit more like what we saw for strength. but still, there's only one of those poles on the real line that's closest to the origin, and that's the one whose growth determines completely the asymptotics of the coefficient. and this is a big one for surjections. and these, these poles, it actually In fact, gets a little bit less accurate. These are this, this one is closer than all these other ones. The on the real line is closer to the origin than all the others. But now they're going to start to contribute possibly to what we see when we do calculations and it's a little bit like the roots of unity and then there's going to be therefor some oscillation. But all of that is explained by properties of the function in the complex plane. And we can do results as precise as we want. Not as long as we're willing to do some calculations. All right. And here's another one alignments. so this is sequences of labelled cycles. It's not quite like permutations, which are sets of labelled cycles. so this is sequences where the order matters. It's called alignments. and this is just an example giving the number of alignments for one, two, three, and four. And by now pretty much everyone can figure out what's going to happen next. we're going to build a common atorial construction, sequence of cycles. cycle is log of 1 over 1 minus, the sequence is 1 over 1 minus that, so there's the generating function for alignments. without really much thought at all. That's a meromorphic function. it's ratio of two analytic functions, so, it's when the denominator gets out to be zero, that, that we care about. This one has got one giant singularity, where log of 1 over 1 minus z equals 1, and that's exactly when z equals, 1 minus, 1 over e. you plug that in, then you get a check, that's the dominant singularity. And there's others out there. so, but then we just do the calculation numerator is 1 differentiate that, you get 1 over 1 minus z. Evaluate it, one over one minus z, just get one over e again. so that tells us that the exponential growth is 1 over 1 minus e to the n. and the constant is this divided by that. Which gives the m plus 1. so that's again, enumerating the alignments. In a combinatorial class maybe we never heard of. But we can immediately get to coefficient asymptotics that's extremely accurate. Uh,[COUGH] and this again shows how accurate it is even for small and And a final example that we looked at is set partitions,[COUGH] how many ways are there to partition an n element set into r subsets, and we talked about this one in Lecture 3. And this is the one that the application is rhyming schemes. How many ways are there to rhyme a poem. so you start by putting the first line in set a and anybody that rhymes with that goes into set a. The first one that doesn't rhyme goes into set b and so forth. and so there's a correspondence between pa, partitioning and allows an our set, our sub sets and and different rhyming scenes on these other applicat, many other applications of this. So how do we do the asymptotics of this one. Well, eh, and we did this combinatorial construction in lecture three, it's, it's, the first, eh, times the sequence of them. Times the second, times the sequences of both of them. Times the third, times the sequence of all three. And so forth up to R. and that immediately translates to a simple generating function. And again this is a rational that is meromorphic. It's the ratio of two analytic functions. We're interested in the root that;s closest to the origin. what root is that? well there's 1, 1 half and so far 1 over r is going to be closest to the origin and actually the one that's closest to the origin is the little one but that's the one that matters. and so now we just again go trhough the procedure. 1 over r is the pole closest to the origin. So, that's going to give us the exponential growth which is going to be r to the n, the inverse of that. The residue is evaluate the numerator at 1 over r and value the derivative of the denominator at 1 over r. there's a little calculation there involving r to the rs that cancel. The result is 1 over r times r factorial. that immediately gives the asymptotic growth that the number of poems with r rhymes is asymptotic to r to the n over r factorial. And so that's four familiar classes and generalizations that are immediately handled by meromorphic asymptotics. All showing, with analytic combinatorics, we can do a construction, immediately to a generating function, immediately to asymptotics of the coefficients.
