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.