Just want to finish up by talking little 
bit. 
giving some perspective on the things 
that we've talked about so far today. 
so 
the ideas that we have a, a calculus that 
is going to be very effective for 
quantitative study of all kinds of a 
large combinatorial structures. 
Always going through same kind of process 
where we have a construction that 
translates to a generating function, that 
translates to coefficient asymptotics. 
actually with complex asymptotics we 
don't even have to solve explicitly for 
the generating function often. 
merely the form of the equation is going 
to give the generating function that 
[COUGH], is going to give a transfer 
theorem that gives the coefficient 
asymptotics immediately. 
and just think about what we've talked 
about in the last four lectures versus 
this lecture to count binary trees. 
so we had a whole slide to go from the 
currents to generate function involving a 
convolution. 
and then expanding that generating 
function involves some kind of intricate 
calculations using binomial coefficients 
that you might remember. 
and got us to the exact form of the 
Catalan numbers. 
and then we had to do the asymptotics 
using Sterling's Approximation that also 
involved significant amount of 
calculations. 
you may remember the first time you saw 
each one of these the amount of intricate 
calculation that seem to be involved. 
Although there's straightforward from 
step to step. 
there's a lot of steps with analytic 
combinatorics. we don't do those 
calculations anymore. 
We simply create the combinatoric 
instruction. 
get to the generating function equation 
and then get the transfer theorem to get 
the asymptotic result, that we're 
interested in. 
And these are normally very accurate and 
certainly accurate enough for practical 
applications. 
so we're in for the arrangements. 
in that case 
we we don't even know 
I didn't even do the example of the 
calculation it's so complicated but we 
get immediately to the coefficient 
asymptpotics. 
And this is a good example of something 
that is characteristic of analytic 
commontorics. Becuase we had a basic 
construction, a permetation a set of 
cycles that we modified to work with the, 
to, 
to get this this answer. 
that's very common we start with some 
fundamental constructs. 
They're a basic things that, that we want 
to study. 
they're either elementary or they're 
trivial or they confirm our intuition. 
and we, we understand them but we 
try to understand'em from the standpoint 
of analytic commontorics. But then we can 
have compound constructs where we have a 
set of cycles or a sequence of sets and 
so forth. and again those are only the 
constructions that I've presented there's 
many, many other constructions available. 
and those things there's lot's of 
possibilities. they'll tell us something 
about the structure like a permetation is 
a set of cycles. and actually lots 
classic commonotorics can be dealt with 
in this way. 
And then there's variations like 
generalizing the arrangements by adding 
another parameter. the possibilities 
immediately become almost unlimited and 
not only that when we get to a generating 
function and equation, we often have a 
universal law that will give us the 
asymptotics. there would be no way to go 
in and get the, exact result and then do 
asymptotics from the exact result. 
in principle you could do that because 
what underlies the analytic combinatorics 
is a bunch of very simple techniques. 
But why would you if your goal is the 
asymptotic result? 
so that's a, a, a very standard paradigm. 
and also combinatorial parameters can be 
handled. 
and we'll see lots of examples of that. 
so that is, we're not just counting 
things. 
We're counting properties of things but 
we talked about in the generating 
function lecture, about the concept of 
cumulative cost where rather than 
computing averages by using 
probabilities. What we do is we count up 
the total cost among all structures and 
then divide and it's reducing 
finding an average for number expected in 
a random object to, to counting problems. 
So, let, so for, to find the leaves on a 
binary tree we count trees using the 
standard process to get to the estimate 
of the Catalan numbers. 
but it turns out that the symbolic method 
works for bivariate generating functions, 
so the same construction will give a 
explicit, equation for the, total cost. 
So, that's the leafs in all trees, you 
just keep track of, of the leafs and 
other variable, and the same construction 
follows through. 
And then differentiated value doesn't 
want to get the leafs on all trees the 
way we did before. 
we're going to get again an explicit and 
then we have the immediate transfer for 
that one too. 
so, we don't have to go into the detail 
we have these two asymptotic results and 
then we just divide. 
and that's how we get to N over four. 
And again, we can do this without all the 
detail that we presented before. 
So this is the slide that I started up 
with that maybe makes a little more sense 
now that we've gone through a number of 
examples. 
You need a lot of combinatorics. 
We begin with combinatorial 
constructions. 
We use symbolic transfer theorems to get 
generating functions. 
They're the central object of study 
because we transferred to them from 
combinatorial constructions and we 
extract coefficients from them using 
analytic transfer theorems. 
and so we can, in principle we can do 
this to any precision on the standard 
scale, and we can handle variations as 
well. 
So now for the rest of the course, we're 
going to be looking at many applications 
of analytic combinatorix for first we'll 
do trees and then we'll do permutations 
which actually can be represented as a 
certain kind of labeled trees. 
and we'll talk about bit streams and 
associated data structures in mappings 
which are fascinating structures. 
and these all have applications to the 
analysis of algorithms. 
so that's what we'll be doing for the 
rest of the course. 
so that's a perspective on what we've 
been doing 
I just want to finish with some exercises 
that you might do to cement your 
understanding of this material. 
So exercise 5.1 is how many good 
strengths of length N have no occurrence 
of three zeros and that's a fine exercise 
to try out these techniques on. 
were for trees and this is just again to 
go through the steps of 
[COUGH] annalytic combinatorix for 
problems similar to the ones that we did. 
So this is binary tree, where the size is 
the total number of nodes internal and 
external. 
so there is no even number is always an 
odd number of total number of nodes in so 
we get an expression for that 
permutations. 
what about, when the cycles are of odd 
lengths, 
that's an easy one. 
tree parameters. 
so the red notes here have both children 
internal and the blue ones have one 
internal and one external. 
So what's the average number of red notes 
and blue notes? 
We already did the average number of 
leaves is it N over four. 
so the those some more problem. So for 
the next lecture if you write up 
solutions to those excercise and read the 
analytic combonatorix chapter in the text 
you'll have a good feeling for the basis 
for, of the analysis of algorithms that 
we're going to begin starting in the next 
lecture.