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.