Today we're going to talk about Applications of Singularity Analysis. As with rational and metamorphic asymptotic. Really what we're going to be talking about is general schema, that apply to whole families of combinatorial classes. And show how those schema can be used to derive asymptotics for many of the classes that we considered earlier in the course with just a few simple calculations. So this is the our next to last lecture. [COUGH] next time we'll talk about saddle point, which is for generating functions that have no singularities. But we're, we're going to talk about lots of the combinatorial classes that we considered in part A. where we have a generating function equation that's not rational or meromorphic that has singularities other than poles. and last time, we saw a general approach to dealing with such functions but that lies underneath some very broadly applicable. schema, and that's what we're really going to be talking about today. so the first one is Simple varieties of trees. And we've talked about that a couple of applications last time, so let's just look again. so we start with this transfer theorem that's proved with the singularity analysis process developed by Flajolet and Liskow in 1990. but that all, all that mechanism kind of lies underneath. so, if the idea is, we have, a, whats called a simple variety of trees. Where the combinatorial construction is Z. with a product, either cartesian product or a star product. of a sequence, a recursive sequence of the same class, where there's some modifier that says what sizes of sequences to use. so, there's this idea of lambda invertible, you know where there's a few technical conditions. But the main one is that we define a function fee which comes right out of the, symbolic method from the construction into a generating function equation. So, the sizes of sequences that we use translate into different functions, phi. so the construction defines the function phi. and that's a so-called, characteristic equation and lambda is the root of this equation. phi of z equals lambda phi, equals z phi prime of z. So if we have that value lambda, then we have the coefficient asymptotics and the function phi, and it's a function of the, first of all, the coefficient growth is just v prime of lambda. The exponential growth is just v prime of lambda to the n. And then the constant is a simple calculation involving the second derivative evaluated at lambda. and it's also the case that the singularity analysis gives us an approximation to the function itself. and that's going to work out to be important in applications later on in this lecture. so it says that a simple variety of trees has a square root singularity. And we can accurately approximate both the function and its coefficients at that singularity. And as always with singularity analysis, we can take these approximations out to arbitrarily arbitrary many terms. in lecture we'll just work with the tilde approximation. And this applies to any kind of tree. virtually any kind of tree, and we'll look at several examples next. So important to note is and as I just mentioned that the singularity ana, analysis gives you not only the coefficient asymptotics, but also approximation of the function nears its dominant singularity. and that's automatic. This is a schema that works for any, any kind of sequence. and so as usual in most applications what we're going to be focusing on is the calculations involved in the coefficient asymptotics. And these are quite simple calculations. For example, we looked at general trees, and again, back in part 1 of this course, we looked at general varieties of trees. And there are certainly a lot of calculations involved in finally getting out the coefficient asymptotics. There's information between in terms of it's catalan numbers and Sterling's approximation and other things But doing that calculation from scratch involves certainly a fair amount of of a discreet Mathematics. and the idea of Analytic Combinatorics is we can get that coefficient asymptotics in just a few simple steps. this is a review of last lecture, but maybe some people are watching this lecture for the first time. So, a G is the class of rooted ordered trees that's just the construction is cartesian product of Z and a sequence of trees. And tree is a root in a sequence of trees that immediately translates to the generating function equation. G of z equals Z over 1 minus G of z. Now we're going to apply the theorem for simple variety of trees. And what that means is we first have to identify the characteristic function. That's 1 over 1 minus u, we compute its derivatives. so that's easy, 1 over 1 minus u squared and 2 over 1 minus u cubed. and then we get the characteristic equation which is 1 over 1 minus lambda equals lambda over 1 minus lambda squared, that's setting phi prime, equal the phi equal to lambda phi prime and you get lambda equals one half. And then evaluating the characteristic function and its derivatives at lambda we get 2, 4 ,and 16. And plug in those values, we immediately get the co-efficient asymptotic. Now 4 to the n of three halves over 4square root of pi. so that's our, our pattern. That's our template for Analytic Combinatoric that we strive for for every problem. They have a construction, take us right to a function generating equation. Take us right to coefficient asymptotics and that's what the simple variety of trees transfer theorem does for this example. so what about binary trees? That's another familiar example that we've looked at since the early lectures in part one of this course. well, one way to construct Binary trees is to say it's an external node. Or it's an empty tree. or a binary tree on the left or an empty tree or a binary tree on the right. you might have been expecting some construction like a binary tree, is like a node or a node in a sequence of either zero, or two binary trees. That's another way to construct binary trees. we'll actually look at that one later on. but this one translates right to the generating function equation, B of z equals z times 1 plus B of z squared. If you have z times the function involving the original on the right then that's simple variety of trees. so we take the simple variety of trees theorem we have to identify the characteristic function. In this case it's 1 plus u squared. compute the derivatives, 2, 1 plus u, and 2. characteristic equation. fi of u equals, equals u phi prime of you and that, now works down to this equation. that lambda squared and through lambda comes out lambda equals one. And then evaluate the characteristic equation and its derivatives at lambda and we get 442 in this case. and so that means the exponential growth is 4 to the n. and the two is canceled. and we simply get one over square root of pi four to the n, n to the three halves. Again, media transfer from the construction, to a generating function equation, to coefficient asymptotics. that's Analytic Combinatorics. in here's another example review from last lecture that's those first 2 examples we know how to do with relatively elementary methods. this one examples like this are much harder. So this is Unary-binary trees where a tree has either 0 every node has either 0, 1, or 2 children. So a tree is a node. Plus a sequence of either zero, one, or, or two, trees. so that's, simply expressed. immediately translates to, the generating function equation. M of z equals z times 1 plus M of z plus M of z squared. that's a simple variety of trees. So we identify the characteristic equation, one plus u, plus u squared. Compute the derivatives, 1 plus 2 u and 2. characteristic equation if you set v of u equal to u times v prime of u and solve. in this case it's lambda equals 1 again. 1 plus 1 plus 1 equals 3, 1 plus 2 is 3. Then, evaluate the characteristic function, and it's derivatives, add lambda and we get 332 in this case. So phi prime is 3, so that means 3 to the n is the exponential growth. and in this time, the constant turns out to be square root of 1 over square root of 4 pi over 3, into the three halves. So all simple varieties of trees are going to have N to the three halves. They're going to have exponential growth, and the difference is what's the factor and what's the constant. again, straight from the spec. To the generating function equation to the coefficient asymptotics without anything in between. Now there is a lot of machinery under there in terms of the singularity analysis process Lagrange was in there to prove this. quite a bit of sophisticated mathematical machinery was necessary to establish this transfer theorem. But once it's proved it's very easy to apply and that's the theme of this whole lecture. Sure we have some very applicable transfer theorems that are quite easy to apply and can lead to the analysis of all sort of combinatorial structures that would be very, very difficult to analyze otherwise. and just to finish the story, this is simple variety of trees also works for labelled structures too. so we looked at Cayley trees, so that's labelled rooted, unordered trees. and so there's N to the N minus 1, we looked at this in lecture two. so this is the analysis that we did in lecture two and I'm just going to flash through it. So it's a, a Cayley tree is a root-connected to a set of trees And for the labeled structures, the transfer from the construction into the generating function equation is for exponential generating functions. in SET means take e to the power, so we get c of z equals ze of c of z. and then in lecture two we used Lagrange inversion theorem. to get the coefficients out, in [COUGH], that eventually getting to into the N minus 1 for the number of Cayley trees. [COUGH], so it's in factorial times that coefficients, N to the N minus 1. so in that certainly a valid way to extract coefficients. but my point for this lecture is that we don't need different tools for every type of trees. We've one term that works for all type of trees. So lets look at Cayley trees from the stand point of a simple variety of trees. same construction its a node is a node star product with the set of nodes. so that same translation, C of z equals ze to the c of z. But now as the simple variety of trees, this one's even simpler than the ones that we just looked at. we can it satisfies z star product sequence or set of something. and so we immediately get the characteristic function phi of u equals e to the u. The derivatives are all e to the u so as long as our generating function has this form then the rest of the theorem comes through. so our characteristic equation is either the lambda equals lambda e to the lambda's. So lamda's 1. and then plug in to evaluate the characteristic function of the value 1. You get e all the time, so phi double prime over phi is just e, and phi prime is e so it's e to the N. So, immediately, get 1 over square root of 2 pi e to the N, N to the minus three halves, immediately. boom, boom, boom, for Cayley trees, using the same theorem that we use for General trees, or Unary-binary trees, or any kind of tree. Just a matter of figuring out the characteristic function, doing the derivatives. Solving the characteristic equation, plugging back in into the formula. it's a very general and significant theorem. You don't need to know the underlying mechanisms behind it, in order to get coefficient, asymptotics. You can work at a different level, which is a level closer to the problem. How do I construct my constructure, my structure, and what's how can I estimate the number of structures of that size? and then I can use that information for all sorts of things, like taking a log to find out how many bits there needed or other information. And we'll, we'll talk about examples in a little bit. So just as an aside, to show that everything's hidden under the covers. Even Stirling's formula's hidden under the covers. we looked at the exact derivation through Lagrange inversion. and then, in this lecture, we talked about the approximate derivation through singularity analysis. The exact one says we get into the N to the N minus 1, the approximate one says N factorial e to the N over square to 2 pi N cubed. so that's, those derivations are a proof that that holds, and that's just Stirling's formula. so counting Cayley trees in two different ways gives us Stirling form-, Stirling's formula. That's, that's one way to look at it. but that's really, in today's context, what we're interested in is the, we took 4 pretty different types of trees and got coefficient, full analysis of them. Including down to coefficient asymptotics using the same theorem. that's an introduction to schema based on singularity analysis.
