It's got two terms in the first term the P+1 cancels against the P+1 pectorial.

In the second term the P+1, both in that one also the P+1 cancels.

So the first term is just ZB of Z.

In the second term, if you group by k,

it's just kz to the k because there's k factorial size and

there's an extra z to run out in the one half from pp plus one over two.

So now, that simple equation solved for b of z Is z B(z) + one half,

that generating function is the derivative of z to the k,

so z squared over (1- z) squared.

Now solve for B(z), and get another factor of one minus Z and

again it's one of our elementary generating functions.

Coefficient of Z to the N in that is the average number of immersions

is N times N minus one over four.

So, now that's the fourth and that's enough and

agin if want many more there's many more in the book.

Again, that checks against small values.

There's lots of properties and permutations that have been studied in

classical combinatorics that can be handled in a similar manner.

So for example, a rise in the permutations when the value goes up, but

falls when the value goes down.

A peak is when the value goes up and then down.

A valley is when the value goes down, then up.

A run is if you have successive values going up.

Left to right minima, we already talked about,

and increasing sub sequence is some subset of the permutation where

they go up all of these properties can be handled in a similar manner.

And again, the book contains several other derivations.

It wouldn't be productive to cover in lecture.

So those four indicate a an approach towards studying parameters

of permutations that's effective in those that we looked at

have actual applications to understanding the performance of

important algorithms in practical situations.