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. 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. 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 equal to M, which is e to the -z minus and so forth over 1- z, and then we showed an analytic transfer theorem that tells us that the asymptotic of that is N factorial over e to the H of M. 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. 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? 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 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. In term of applications, there's the idea of a reciprocal cipher. So if you use an involution, 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. 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 involution or permutation which is an involution. And that same thing says D goes to A, K goes to T and so forth. 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. 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. 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. That's going to be c squared over two. So we get the c squared, so it's n over two factorial. And that's the equation and we can do the asomtatics from sterling's approximation to get the number of two cycles. So a very simple and straight forward with basic comatorics and asomtatics. But what about involutions? 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. 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. 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. 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. So with the analytic combinatorics we can get directly to results like that although the asymptotics of that is definitely not trivial. 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. The coefficient asymptotics of that one is one of the most difficult 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. So that's a very specific question and 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. But if you do the same thing with the 1/1-z, then we only need to keep the first ten terms of that one. 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. As an application, we're going to consider a problem known as the 100 prisoners problem. This actually was a Google interview question for a while. 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. 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. 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. 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. 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. 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? 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. Now he's going to continue until he finds the drawer that contains his own ID 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.