Well, it's a set of cycles that are not of size r plus cycles that are size r
marked with the cost variable u, and that's it.
And so by transfer theorem,
that immediately gives log of 1- z with the 1 for
r subtracted off, and then add it 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 up to the z to the r over r,
evaluate at u = 1 just makes it e to the log of 1 / 1- z,
and that's the generating function for the average number of cycles.
And what's the coefficient of z to the N in that?
It's 1 / r as long as N is bigger or equal to r.
So 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'll be mostly in Part Two.
And just to quickly finish up without going into much detail, this parameter,
the number of permutations with size N with k cycles has got a long history and
lots of applications that we don't have the time to talk about in detail.
So 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 2 of them that have 1 cycle,
3 of them that have 2 cycles, and 1 of them that has 3 cycles.
And for 4 goes 6, 11, 6, and 1, and so forth.
So what we just did was show that [COUGH] if we just define the BGF for
Stirling numbers of the first kind,
we just showed that it's 1 / 1- z to the u.
And you can use that form to develop all kinds of interesting identities for
the Stirling number.
For example, the distribution for a given N,
the number of cycles of size N [COUGH] is
the coefficient of z to the N / N factorial, which,
if you use Taylor's theorem to expand this,
you get u times (u + 1), (u + N- 1), and so forth.
So if you take that polynomial in u, the coefficients of that
polynomial give you the Stirling numbers of the 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 so forth.
We'll come back to some more details about this in Part Two.
I just wanted to point out that this kind of structure,
in more detail, has been studied a great deal.
In fact, here's a distribution with rescaling by N,
and actually one of the results in combinatorics
we studied tried to learn about limiting
distributions in situations like this.
And actually it can show that this distribution is normal in certain ranges.