0:04

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.

Â 5:38

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.

Â 9:13

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.

Â 10:52

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.

Â 11:47

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.

Â