So now I want to finish up this lecture 
by giving indication of how these kinds 
of problems can be solved with analytic 
combinatorics in this, in the symbolic 
method. 
essentially those derivations in a sense 
were a, a little bit the hard way, and 
there's an easier way. 
Now we'll develop this fully in part two 
but it's, it's worthwhile to take a look 
at typical derivation using analytic 
combinatorics because it's actually not 
that much more difficult. 
And, actually, the idea is to use 
bivariate generating functions. that's 
really the way to analyze combinatorial 
parameters. 
so the idea is, for combinatorial class, 
we have not just the size function, but 
we also have an associated parameter that 
has a cost and we want to analyze the 
cost associated with the size. We're 
looking for the average number of cycles 
in all permutations of size N and so 
forth. 
So, the way that we do that, say for 
unlabeled objects, is to just take 
another variable, u and define the 
bivariate generating function, z and u, 
where z is for size and u is for cost. 
So for every object we take z to the size 
of that object and u to the cost of that 
object. 
So that's what we work with for labeled 
classes we divide by the size factorial 
but it's the same idea. 
So that's the form that we're going to 
work with for permutations. 
Now the idea is that those constructions 
that we gave are going to work just as 
well to give us formulas that these 
bivariate generating functions have to 
satisfy and not only that. The bivariate 
generating function really does carry 
full information about the association 
between size and cost. 
and again, it's pretty much as easy to 
compute as the as the CGF and we'll look 
at those computations next. 
and not only that using this approach 
with analytic combinatorics, it's often a 
case that we can get full distribution of 
the asymptotics or the full distribution 
by knowing and generating a formula that 
the bivariate generating function has to 
satisfy. 
So it's extension of the symbolic method 
beyond just counting to also take into 
account cost of parameters in 
combinatorial structures. 
So what are the, the basic calculations? 
So we start with a a bivariate generating 
function. This is exponential for 
labelled classes like permutations 
because that's all the examples I've done 
so far today. 
so if you want to go back to the way that 
maybe you are used to thinking of things 
and, and we had in our tables actually 
the number of elements of size N with 
parameter value k then that [COUGH] have 
the fundamental identity, which just 
extends what we did for single varied 
generating functions. 
if you're summing in all combinatorial 
objects you can gather them together by 
size and by cost and then the number with 
[COUGH] size N and cost k, that's the 
coefficient of z^N/N u^k because everyone 
of those objects will contribute one to 
the sum, you gather them together, you 
have A Nk objects that have that sum. 
And so that identity is implicit when 
we're trying to understand the 
combinatorics of it we work with the 
representation where we have a term and a 
sum for every object but when we want to 
do some counting we use the elementary 
identity to get us the results that we 
need. 
So for example the, as I just said, the 
number of objects of size N with value k 
we can get from a bivariate generating 
function. 
It's the coefficient of z^N, coefficient 
of u^k divided multiplied by N for the 
label. 
so but what's interesting is what's the 
average value of a parameter for a 
permutation. 
It's the coefficient of z^N and the 
partial derivative of the bivariate 
generating function with respect to u 
evaluate at u=1. 
it seems like maybe kind of a strange 
operation to perform but the calculation 
is, is really simple. 
So if you take the partial of A(z,u) with 
respect to u you get ku^k-1. 
so now if you evaluate that at u=1 then 
that u^k-1 goes away, 
and if, now if you look at that sum, 
what's the coefficient of z^N in that? 
it's the sum of k A and k. 
and then, again, the trick, the divide by 
N. 
So it's the sum of k, the probability 
that it's k over sum of k, the 
probability that it's k which is exactly 
the average. 
So just knowing that one little really 
trivial calculation means that we can go 
ahead and [COUGH] use our constructions 
to tell us about the bivariate generating 
function and just do that one, 
differentiate with respect to u and 
evaluate at u=1. 
so this is the construction that we did 
earlier on say for average number of 
cycles and, and this is the same slide as 
above so I won't spend too much time 
talking about it. 
so we apply our construction and then 
simplify the sum to get down to the 
harmonic numbers. 
so let's do it with bivariate generating 
functions. So bivariate generating 
function, it's z to the size over size 
factorial u to the cost. 
So now our same construction which has 
for [COUGH] for cycles, for every 
permutation, we construct a bunch of 
other ones and p of those have the same 
number of cycles and one of them has one 
more cycle. 
So that's what this equation says, that 
those, those permutations of size p+1 one 
of them has one more cycle, that's u to 
the cycles of p+1 and p of them have the 
same number of cycles, that's p u to the 
cycles of p. 
So rearranging the terms and the sum 
according to this construction implies 
that identity on the bivariate generating 
function. 
And that one is not so difficult to 
[COUGH] simplify so z^|p|+1/ (|p|+1), 
that means we should differentiate with 
respect to z, and if we do that then we 
get two simple sums that we can easily 
simplify. 
the first one is just zB (z u), uh,, and 
[COUGH]· I mean, sorry, uB (z u), and the 
second one has is like the derivative 
with an extra factor of z and you can 
check that. 
It's a very simple calculation. 
And now we can solve for derivative of u 
with respect to z and we have B sub z (z 
u) = u/1-z, B(z u),. 
That's a differential equation in z that 
we can just solve. 
And it's 1/(1-z)^u. 
And it's a little shocking at first that 
there should be such a simple solution 
but once you think of u as a constant and 
just work with the z it's not it's not so 
amazing a calculation. 
and that's an explicit formula for the 
bivariate generating function. 
And what do we want from that formula? 
what we want is the average value of our 
parameter. 
How do we get the average value of that 
parameter? For any bivariate generating 
function, all we do is differentiate with 
respect to u and evaluate at u=1. 
Differentiate with, that with respect to 
u, evaluate at u=1 you get 1/1-z, log 
1/1-z. 
that and the coefficient of z^N in that 
is your average, which is the harmonic 
numbers. 
So the same kind of construction leads us 
to our result. 
But what really makes bivariate 
generating functions the method of choice 
is, is that we can actually get rid of 
this sort of construction stuff and 
really use this symbolic method and, and 
again we'll talk about many examples of 
this later on but I want to show it for 
this one. 
so the idea is to just carry the cost 
along with the combinatorial 
constructions and the transfer theorems 
and everything else follow right through 
for a bivariate [COUGH] and with, without 
much difficulty at all. 
so this symbolic method will take us 
right to where we need to get. 
so this says, a permutation is a set of 
cycles of z and the variable u marks the 
number of cycles and, and that's it. 
so that immediately leads to the through 
transfer theorem which is the same cycle 
is log 1/1-z and set is e to the, 
immediately leads to e^u log 1/1-z. 
so simple combinatorial construction 
immediate transfer to BGF equation and 
there we are, no sums at all. 
and what do we want? We want to 
differentiate with respect to u, evaluate 
at u=1. 
and in this form, it's the same function, 
it's 1/1-z^u just written in exp log 
form. 
it's obvious that the derivative with 
respect to u is going to bring out a 
factor of log 1-z and then leave leave 
this term, evaluate u at u=1, it's just 
1/1-z. so immediate from the transfer 
theorem to there and then immediate 
derivative evaluated at u=1 which 
immediately gives the harmonic numbers. 
So derivations of this simplicity 
replacing the ones we've been doing is 
really persuasive evidence or the 
persuasive bottom line that BGF's and the 
symbolic method are the method of choice 
in analyzing parameters. 
we're going to see many examples of that 
in part two. 
and so here's say another example. 
So we, you wanted to know the average 
number of cycles of size 1 that we did an 
exercise with 2 and r and so forth. 
So here's that derivation using symbolic 
method. 
So, a number of cycles of size r well, 
it's a set of cycles that are not of size 
r plus the cycles that are of size r 
marked with the cost variable u. 
That's it and so, by transfer theorem, 
that immediately gives log of 1-z with 
minus, with the 1 for r subtracted off 
and then added back on marked with u. 
so immediate from the transfer theorem to 
that BGF equation and then what's the 
value we're interested in? We want to 
differentiate with respect to u, evaluate 
at u=1 and that is immediate 
differentiate with respect to u brings 
out to the z^r/r, 
evaluate at u=1 just makes it e to the 
log 1/1-z and that's the generating 
function for the average number of cycles 
and what's the coefficient of z^N in 
that? It's 1/r as long as N is bigger or 
equal to r. 
So the working with the constructions in 
the way we did earlier is at the level of 
detail that analytic combinatorics can 
free us from and again, we'll see many 
more examples of working with parameters 
that allow us to use the symbolic method 
for bivariate generating functions in 
this way. 
[COUGH]. 
So that, that'll be mostly in part two. 
and just to to quickly finish up without 
going into much detail this parameter, 
the number of permutations with size N 
with k cycles it's, has got a long 
history and lot's of applications that we 
don't have the time to talk about in 
detail. 
so in, it's written, it's called Stirling 
numbers of the first kind and it's 
usually written nowadays in square 
brackets like that. 
So for permutations of size 3 there's two 
of them that have one cycle, three of 
them that have two cycles and one of them 
that has three cycles. 
And for 4, it goes 6, 11 6 and 1 and so 
forth. 
so what we just did was show that 
the [COUGH] if we just define the BGF for 
Stirling numbers of the first kind, we 
just showed that it's 1/(1-z)^u and you 
can use that form to develop all kinds of 
interesting ID, identities for the 
Stirling number. For example, the, the 
distribution of for a given N the number 
of cycles of size N [COUGH] is the 
coefficient of z^N/N, which if you, if 
you, if you use Taylor's theorem to 
expand this you get u*(u+1), (u+N-1) and 
so forth. 
so it, it's, if you take that polynomial 
as a polynomial in u the coefficients of 
that polynomial give you the Stirling 
numbers of the second time, second kind. 
and you can also come up with a way to 
compute them and get a recursive formula, 
like the basic formula for binomial 
coefficients and, and so forth and we'll 
come back to some more details about, 
about this in part two I just wanted to 
point out that this, this kind of 
structure in more detail has been studied 
a great deal. 
in fact, here's a a distribution with the 
with the scaling by N and actually one of 
results in analytic combinatorics we 
study try to learn about limiting 
distributions in situations like this and 
that actually, I can show that this 
distribution is normal in certain ranges. 
so that's the use of bivariate generating 
functions and introduction of an easier 
way to deal with analysis of parameters 
in permutations. 
so I just want to finish up with by 
pointing out a couple of exercises that 
people could do to test their 
understanding of the material that we've 
talked about so forth, so far. 
So the first one is this study 
arrangements. 
so an, an arrangement of N elements is a 
sequence formed by a subset of the 
elements. 
so that's a a permutation use element, 
each element once and only once. 
With arrangement, you could use some of 
them more often. 
and so the problem is to prove to study 
arrangements and to get some kind of 
combinatorial interpretation. 
and the, this next one tests two 
different concepts of that we've brought 
up and that's inversions and involutions. 
So find the average number of inversions 
in an involution. 
and there's no real reason to do that 
other than to test out the mathematics. 
and then this third problem gets at what 
is the cycle length distribution look 
like? so it, it actually turns out to be 
asymptotic to Poisson distribution. 
and from the generating functions you 
can, you can show that and that's an 
interesting problem to work through. 
so for the next lecture read the [COUGH] 
Chapter 7 uh,, in the text. 
again, it's kind of encyclopedic, so you 
might find yourself skipping through 
analysis of certain parameters but some 
of them have interesting applications. 
I think it's always a good idea to run 
some experiments to validate the 
mathematical results that we've developed 
and it's easy to generate random 
permutations so why not do it to just 
check that. 
say the average number of cycles or the 
average number of 1-cycles in a random 
permutation agree with the results 
predicted by, by our analysis. 
and even for distribution for that 
exercise where we're doing the 
distribution of cycle length takes more 
cycle, more [LAUGH] computer cycles to 
study cycles but it's worthwhile to run 
experiments to validate these things 
always. 
and, and again, it is used worthwhile to 
practice writing up solutions to 
exercises like this. 
so that's permutations.