So, instead of LRM, I wrote cycles but it's the very same derivation.

We apply the construction and use that to essentially reorder the terms in the sum.

We say the generator function also has to equal that expression.

Then it simplifies in exactly the same way to get down to the harmonic numbers.

Average number of cycles in a random permutation of size N is A sub N.

Now, when we have the same generating function again,

often in combinatorics, when we see that.

What we like to do is find a correspondence,

a one to one correspondence between the number of LRM and the number of cycles.

So it's a reasonable question, is there a one to one correspondence.

This is a famous one, and the answer is yes.

So what you could do, if you have a set of cycles.

You can build a permutation corresponding to that set of cycles.

A unique permutation corresponding to that set of cycles.

By looking at the smallest element in each cycle, call that the leader of the cycle.

So the first one, the four is the leader.

The second one, the one is the leader.

The single cycle there's only one.

The third one, the 14 is the leader.

And the last one, the two is the leader.

So we identify the leader of each cycle.

And then what we'll do is write down the cycles in decreasing order of the leader.

So we pick the largest leader and then write down its cycle,

just by following the cycle.

So in this case, the largest one is 14.

That's where we write 14, 60.

The next largest leader is just the five.

The next one is that first one, where the leader is four.

So we write down four, ten, six, 15.

And then the big one at the end, we write down two, 12, eight, three, 11, 13.

And then the one containing the one is one, seven, nine.

Now we don't write down, we didn't demark

the cycles in any way, but that's a permutation.

And so, I said it was unique and that means we can use a corresponding

process to get the set of cycles corresponding to any permutation.

What’s the set of cycles corresponding to this permutation?

So we’re given the permutation.

What we do is, identify the left to right minima.

Those are the leaders.

Remember we pick the leader as the smallest in the cycle, and

then we wrote them down in decreasing order of the leaders.

So between each leader, say between four and two.

Everybody on the same cycle as four is bigger.

And so, as soon as we get to somebody that's smaller than four,

that's the leader of the next cycle.

So that's how we break up the permutation into cycles and that immediately

shows that the number of left to right minima is equal to the number of cycles.

because this correspondence is one to one, and works for any permutations.

So that's a famous correspondence between left to right minima in cycles.

That so, now we can write down the cycles just by finding the lrm,

and then simply writing the cycles out as before.