0:03

Okay, next we're going to extend the kind of analysis that we did

when we introduced permutations in the fifth lecture, and

look at permutations as set of cycles with restrictions on the cycle length.

Recall that we study this when looking at, introducing at

with the following kind of construction, permutation is a set of cycles.

0:33

Then from the symbolic transfer theorem for labeled objects,

that means the generating function satisfies for set.

It's exponential for cycle its natural log, so

P* (z) = exp(ln 1 over 1-z) which is 1 over 1- z.

Therefore the counting sequence is N factorial coefficient N

that which is N factorial.

And if you want to extend that to same analysis to count the number of

derangments, that's the permutations we know singleton cycles,

then we just restrict the length of the cycle to be bigger than one,

which corresponds to leaving off the z in natural log of 1 over 1 minus z.

So natural log 1 over 1 minus z minus z is z squared over 2 plus z and so forth.

Another way to look at it is natural log of 1 over 1 minus z minus z and

then, that's e to the minus z over 1 minus z.

1:39

So, coefficient of z to the N that is a convolution, which is minus 1 to

the k over k factorial, which is asymptotic to 1 over e.

And then we did the generalized arrangements.

If we restrict to no short cycles of length less than or

equal to parameter M.

It's just a straight generalization of the argument for

derangements, where now it's e and we started z at either M or M+1.

Or that's log 1-z minus all the ones less than or

2:31

So that's a review of what we talked about in terms permutations

with cycle length restrictions, when introducing analytic common torques, and

now we'll look at another problem of that flavor, and that's involutions.

2:48

An involution is a permutation where all the cycles have to be short.

So, they either have to be a length of one or two in an involution.

So out of the 24 permutation of length 4,

only 10 of them have cycles of all of length 1 or 2.

The others have either 1 cycle of length 3 or 1 cycle of length 4,

similarly, there are only 4 of the permutations [INAUDIBLE] Three,

that don't have any three cycles and so forth.

So, the question we're going to want to take a look at it,

how many involutions there are.

Involutions are actually interesting,

common tutorial objects with lots of applications.

One way to see it is to think again about inverses.

Remember a permutation is a mapping.

If you look at the permutation it's the mapping of one through N to itself.

Then the inverse is the inverse of that mapping.

So if we figure students in room and sort by room and flip the rows,

we get the inverse.

What's the inverse of an involution?

3:56

If you take an involution and compute the inverse by,

again, sorting by the [COUGH] bottom,

sorting the columns so that they're in order by the bottom row and then flipping.

You see that immediately you get back the involution.

So what's the inverse of an involution?

It's itself.

And if you think about the cycle representation

4:26

taking to mapping the cycle representation is just moving one step in the cycle.

So if you move one step, if you have a two cycle and you move one step,

then another step you get back to where you were.

If you have a one cycle, you just stay where you were.

So always with two steps, you're going to get back to the same place.

So that's why involutions are significant, and the significance.

So in the lattice representation,

the one cycles correspond to elements that are on the diagonal.

And then the two cycles have to be symmetric, one goes to nine,

nine goes to one.

And if you transpose it you get the same thing back.

So an involution, it's own inverse, and

you see that from the lattice representation, immediately.

5:24

then what you can do is encrypt and decrypt with the same machine.

And actually a famous example of that is the Enigma Machine.

Enigma Machine that was used by the Germans in World War II,

one of its components was involution.

5:40

So the idea is you have your, or letters from A to Z and minus for blank again.

If the [COUGH] permutation that we used to

encrypt is an involution, then we don't need to compute the inverse.

The involution is its own inverse.

So we don't need a separate table to decrypt.

If we have our plain text and then we get the ciphered text,

A goes to D and so forth, then to decrypt, we use the same

6:24

So the involution is a permutation that is its own inverse.

And again it's still susceptible to the character frequency attack but

it's proven useful as a component in a cipher machine because it can greatly

multiply the number of possibilities that an eavesdropper has to consider and

that's how it was used in the Enigma.

So for example if you want to know how many different Enigma settings you

have find, then you have to know something about enumerating involutions.

And there's a very famous story about the crypt analysis of the Enigma

involving Alan Turing and so forth.

And if you don't know that story, definitely worthwhile to look it up and

read about it.

So, as a warm up, let's take a look at the number of permutations

that are composed entirely of 2 cycles.

So, there's only one permutation size 2 that's all 2-cycles.

There's three different ones of size 3 that are all 2-cycles and so forth.

And actually, an example of this is called ROT-13, so, it's the world's

weakest cryptosystem, where we just take the letters and rotate them 13 positions.

So A goes to N, N goes to A, B goes to O, O goes to B and so forth.

And you can read about this one on the web, it's a hacker's delight because

anyone can Encode or decode and people get so they can read in this and so forth.

So, it's a very light crypto-system that hackers use to just lightly

put stuff out on the web that maybe is inappropriate content, but

you have to be at least able to decrypt in this way and

nobody would get offended if they ran across it accidentally.

So again, since this 2-cycles it's a reciprocal cypher.

So you use the same table to decrypt and encrypt.

8:32

So, how many permutations are in control's entirely of 2-cycles?

Well, a permutation, we'll call it R.

It is just a set of two cycles.

8:46

Two cycles is either c squared over 2, so

the equation is either z squared over the 2.

So, all we want, is the coefficient of z to the n in that.

9:29

Well, the construction is pretty similar.

It's a set of one cycle starred with a set of two cycles.

So they're just permutations where all the cycles are of length one or two.

So that immediately goes to e to the z + z squared over 2.

So, cycle 1 z, cycle 2 z, and then set of those is e to z plus z squared over 2.

9:58

First one, e to z, second one is e to the z squared over 2.

So now we want to extract the coefficient so

what's n factorial coefficient to z to the n in that function.

Well, that gets to be a discrete sum that is maybe not so easy to analyze.

10:17

n factorial over k factorial, two to the k and minus two k factorial.

So it's a convolution of a term like the one that we had for just two cycles and

then whatever in factorial.

And that's easy to verify.

10:31

So we the asymptotic of that is a bit more complicated.

It's got a square root.

Two fourth root of e in it, and it's definitely,

have a intricate looking function, and

that's available from the Laplace method for sums.

Remember the plus method we isolate where some most way of the sum is.

And then I estimate with an interval there and also bound the tails and so forth.

And that's done in confined three or later on in part two,

we'll see how with complex SM static directly get that answer of.

11:27

If we are to generalize, how about no big cycles

where we parametrize the cycle length by m, same way did for deviations.

So now the construction is a set of one cycle,

start with a set of two cycles and so forth up to a set of m cycles.

E to the z squared plus e squared over 2 plus out to z to the M over M.

That's direct from the symbolic method.

12:06

derivations in our analytic combinatorics book.

But we can know the isotonics of that through analytic common work.

As an example, now for some applications you might need to actually work

out the full isotonics and just as an example I want to show an exercise.

So this is the generating function for the number of permutations

that have no cycles of length bigger than 5.

So let's say we have permutations of length 10

We want to know how many of those have no cycles of length bigger than five.

So the answer to that question is coefficient z to the ten,

in that function.

13:04

still it's worthwhile looking at a calculation like that to get some

facility for types of problems that sometimes arise.

So if we write the generating

function in, say, the other form, the alternate form,

it's log of one over one minus z minus, then the bigger terms.

So that's equivalent.

Log of 1 over 1 minus z is a sum of z to the k over k.

And if we subtract off the ones bigger than 6 then we get the one's less than or

equal to 5.

And now with that we can take e to the log 1 minus z as just 1 over 1 minus z.

And then we have the other terms multiplied out.

Now the key idea here is that each one of those terms,

if we use Taylor's theorem to expand them.

We only need to keep the first term.

E to the minus z6 over 6 is 1- e 6 over 6 + z 12th that will over

a 2 factor are in trouble.

We don't need the next term, because Z to the 12th,

and we only are interested in Z to the 10th.

So, anything that Z to the 12th multiplies by is going to be

bigger than Z to the 10th, and we don't even need to carry that term.

So, this is exactly inequality.

We just keep the ones that could possibly contribute to a coefficient

of Z to the 10th.

So now the exponentials are gone, and we have this list of polynomials.

15:01

And then for these you cross multiply each one of these and really you only

need to keep the one where you picked like Z to the eighth over eight and it

multiplies by one in all the other terms so that's the Z to the eighth over eight.

Multiply any one of those others it's going to get somethings bigger than Z

to the tenth and can't contribute coefficient of Z to the tenth.

So now, I would just have product of two terms and

coefficient of C to the 10th is easy in that because

the cross-multiply this one contribution from each one.

It's just 1- 1/6- 1/7 and so forth.

So the- 1/6 comes from Z to the 6th over 6.

Times z to the fourth, and z to the one-seventh,

z to the seventh over seven times z cubed and so forth.

So if you look at that derivation, you pretty much convince yourself

You can easily convince yourself that that's an effective way

to calculate a coefficient like that for a particular problem.

16:16

So the idea is, it's a story where you have 100 prisoners.

Each have a unique identity card.

So, the prisoners are numbered from 1 to 100 on, each have a card.

Now they've been sentenced to death because they're on the wrong side during

the Civil War, or whatever.

But they're given a last chance.

16:37

And so, the last chance is that the ID cards are all

collected in this cabinet that has 100 numbered drawers.

The cards are collected and shuffled, put in random order, and

then they're put in the drawers, one card per drawer.

16:54

So now that's the set up.

And now the prisoners, one at a time, are allowed to go into the room that has

the cabinet and open a drawer, look at a card, and then close the drawer.

And they get to do that for, at most, 50 drawers.

17:10

So each prisoner can look at 50 drawers, but not all of them.

And so then when the prisoner comes out they have to announce what

drawer their number is in, and if all of them find their own number,

then they won't be executed, but they have to all find their own number.

If anyone of them doesn't, then they're all executed.

17:37

Okay, if one prisoner can't find the number, they're all executed.

So, now one of the prisoners is a mathematician, prisoner A.

And he says, well, this is hopeless.

We're all going to die because we can each only open 50 drawers, and

they're randomly ordered.

So that means that we each have only half a chance of one-half of finding

our number.

And there's 100 of us, so the chance that we'd all find our number is 2 to

the -100th, and that is exceedingly an unbelievably small number.

We have no chance.

18:12

If fact, it won't take too long before somebody can't find their own number.

But there's another prisoner who knows some analytic combinatorics and

he said, I think I have an idea.

I know a strategy where at least we have a 30% chance of success.

So that's the Google interview question is, what's the strategy?

18:37

So really, what prisoner A was saying was that his strategy was going

to by pick drawers at random, and obviously that's not the best strategy.

So what's prisoner B's strategy?

Well, from the context maybe many of you have figured it out.

So, the strategy is that each prisoner should follow the cycle.

That is, each prisoner, he knows what his number is, say it's number five.

So he should open the drawer that has number five, and

then use that number to decide what drawer to open next.

And then just keep going.

19:26

and so that's going to be the strategy.

Well, he also, he has to stop if he gets to 50 drawers.

So if you think about then, when does this strategy succeed and when does it fail?

Well it's going to succeed if the permutation that represents the cards in

the drawers, it has no long cycles.

No cycles of length greater than 50.

So what's the chance that a random permutation has no cycles of length

greater than 50?

Well it's the coefficient of z to the 100th,

in e to the z plus z over two, plus so far as z over 50.

And that's just a slight generalization of the little exercise that we just did,

to see that that coefficient is going to be 1 minus 100

harmonic minus the 50th, which is about 1 over log 2.31.

That's a solution to the 100 prisoners problem and

application of study of the cycle structure of permutations.