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.

Â