Okay. 
Next, we're going to, expand the kind of 
analysis that we did when we introduced 
permutations, in, this lecture. 
Look at permutations such as cycles with 
restrictions on the cycle length. 
I recall that we study this when looking 
at introducing analytic common torts, 
with the following kind of construction. 
A permutation is a set of cycles. 
then from the symbolic transfer theorem 
for labeled objects. 
that means that the generating functions 
satisfies for set, it's exponential, for 
cycle it's natural log. 
So P(z)=e^ln1/1-z), 
which is 1/1-z. 
So therefore, the counting sequence is 
N![z^N], that which is N!. 
and if you want to extend that to same 
analysis to count the number of de-, 
derangements that the pigmentation, we 
know singleton cycles, then we just 
restrict the length of the cycle'd be 
bigger then 1, which corresponds to, 
leaving off the, the z, in natural log of 
1/1-z, so natural log 1/1-z-z, is 
(z^2)/2+z and so forth. 
in or in other words, look at it's just 
natural (ln1/1-z-z), and then, that's 
e^-z/1-z. 
so the coefficient of z to the N that is 
a convolution, which is (-1)^k/k!, which 
is asymptotic to 1/e. 
it's and then we did the generalized 
derangements, if we restrict the no show 
short cycles of length <= parameter M. 
And the it's just a straight 
generalization of the argument for 
derangements. 
Where now it's e, and then we started 
z^n+1/n+1. 
or that's ln1/1-z-z all the ones <= to M. 
which is e^-z- and so forth /1-z. 
and then we showed an analytic transfer 
theorem that tell us that the asymptotics 
of that is, N!/e^HM. so, that's a review 
of what we talked about in terms of 
permutations with cycle length 
restrictions when introducing analytic 
combinatorics. 
And now we'll look at another problem of 
that flavor. 
and that's involutions. 
an involution is the permutation where 
all the cycles have to be short. 
So they either have to be length 1 or 2, 
and then involution. 
So out of the, 24 permutations of, of 
length 4. 
only 10 of them have cycles of length or 
of length 1 or 2. 
the others either have either, one cycle 
of length 3 or one cycle of length 4. 
Simiarly there are only 4 of the 
permutations of size 3. 
that don't have any 3 cycles and so 
forth. 
so the question we're going to want to 
take a look at is how many involutions 
there are? involutions are actually 
interesting combanitorial objects with 
lots of applications. 
One way to see it is to think again about 
inverses. 
Remember a permutation is a mapping, if 
we look at the permutations of mapping 
the numbers 1 through N to itself, then 
the N is the inverse to that mapping so 
if we think of students in rooms and sort 
by room and flip the rows, we get the 
inverse. 
What's the inverse of an involution? I've 
it's in if you take an involution and 
compute the inverse by again, sorting by 
the, bottom. 
Sorting in columns so it's really by the 
bottom row. 
And then flip them. 
you see immediately that 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 the mapping and 
the cycle representation is just moving 
one step in the cycle. 
So if you knew of one step, if have a two 
cycle you move one step and then another 
step you go back to where you were. 
If you have a one cycle, you just stay 
you were, so always with two steps you're 
going to get back to the same place 
SO that's why evolutions are significant. 
in the significance of, so in the lattice 
representation the 1 cycles correspond to 
elements that are on the diagonal and 
then the 2 cycles have to be symmetric. 
1 goes to 9, 9 goes to 1. 
and if you transpose it, you get the same 
thing back. 
so involution is it's own inverse. 
and it, it's you see that from the latest 
representation immediately. 
and in terms 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 Enig machine, Enigma Machine that was 
used by the Germans in World War II. 
one of it's components was an involution. 
so the idea is you have your, our letters 
from A to Z and minus are black again. 
if the permutation that we used to 
encrypt is an involution then we don't 
need to computer the inverse. 
The involution is its own inverse. 
SO we don't need a separate. 
A table to decrypt. 
If we have our plain text and then we get 
the cipher text A goes to D, and so forth 
then do decrypt, we use the same [COUGH] 
involution or permutation which is an 
involution. 
and that same thing says D goes to A, K 
goes to T, and so forth. 
so, involution permutation has it's own, 
it's own inverse. 
and, again, it's still susceptible to the 
character frequency a,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 enigmas, different enigma settings 
you have Fine then you have to know 
something about enumerating involutions. 
and most they, from Australia about the 
cryptonalysis of the enigma involving 
Alan Turing and so forth. 
And if you don't know that story, 
definitely worth your while to look it up 
and read about it. 
So, as a warmup, let's take a look at the 
number of permutatoins that are composed 
entirely of two cycles. 
And so, there's only one permutation size 
two that solves two cycles. 
There's three different of size three 
that are all three cycles and so forth. 
and actually an example of this is called 
rot 13. 
So it's the, the world's weakest crypto 
system. 
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. 
So forth. 
and, you can, read about this one on the 
web. 
It's hacker's delight because anyone, 
encode or decode and people get so they 
read in this and so forth. 
So it's a very, light crypto system that 
hackers use, To just lightly, to put 
stuff out on the web, that maybe's 
inappropriate content. 
but you have to be at least able to 
decript in this way, and nobody get 
offended if they ran across it 
accidentally. 
so again, since it's 2 cycles, it's a 
reciprocal cipher, so You, you, just use 
the same table to decrypt and encrypt. 
so what's, how many permutations or 
controls entirely of two cycles? Well, a, 
a, permutation, we'll call it r, is a, 
it's just a set of two cycles. 
2 cycles is e^z^2/2, so the equation is 
e^z^2/2. 
And so all we want is the coefficient of 
N factorial times the coefficient of Z^n 
in that. 
So that's going to be Z^2 over 2. 
So we've go the Z^2, so it's N over 2 
factorial, and that's the equation, and 
we can do the asymptotics from Sterling's 
approximation to get the number of two 
cycles. 
So, very simple and straightforward with 
basic, electronic torques and 
asymptotics. 
but what about involutions. 
well the construction is pretty simillar. 
it's it's like a one cycle installed with 
a set of two cycles. 
So they're just permutations where all 
the cycles are length 1 or 2. 
so that immediately goes to e, e^z+z^2/2, 
so cycle 1, z, cycle 2, z, and then a set 
of those is e^z+c^2/. 
First one z to z second one z square over 
two so now we want to extract the 
coefficient so whats n factorial 
coefficients of z to the n in that 
function. 
well that, that gets to be a discreet sum 
that is maybe not so easy to analyze. 
N!/k!^2k(N-2k)!. 
So it's a convolution of a term like the 
one we had for just two cycles and then 
1/N!. 
And that's easy to verify. 
So the aymptotics of that, is, a bit more 
complicated. 
It's got a square root 2 fourth root of e 
in it and its its defininately, a, 
intricate looking function, and that's 
available, from the Laplace method for 
sums, remember the Laplace method, we 
isolate where, the sum, most weight of 
the sum is. 
and then, estimate with an integral there 
and also bound the tails and so forth. 
and that's done in coming Part 3. 
later on in Part 2, we'll see how to with 
complex asymptotics, directly get that 
answer out. 
so with the analytic combinatorics you 
can directly to results like that. 
although, a The asymptotic's of that is 
is definitely not trivial. 
and then, if we want to generalize you 
know, how about no big cycles where we 
parameterize the cycle length by m same 
way as we did for the derangement's. 
So now the construction is, its a set of 
one cycle, start with a set of two cycles 
and so forth up to a set of m cycles. 
E^z^2+E^2/2 plus out to z^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 analytics cominotorics books. 
but we, we can know the asymptotics of 
that through analytic combinatorics. 
as an example now for some applications, 
you might not need to actually work out 
the full asymptotics, and just as an 
example. 
I want to show an exercise, so, 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 like bigger than 5. 
So the answer to that question is 
coefficient of z^10, in that function. 
So, that's a very specific question, and 
still it's worth while 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 a log(1/1-z) - then the bigger 
terms. 
so that's equivalent. 
1 / (1 - z) is the sum of z^k / k. 
and if we subtract that ones bigger than 
six then we get the ones less than or 
equal to five. 
now with that we can e^ ln(1/(1-z)) is, 
is just e ^ (1/(1-z)) and then we have, 
the other times, 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 ^ -z ^ 6 / 6 is 1 - z ^ 6 / 6. 
Plus z ^ 12 /, over 
In 2! by 12 but we don't need the next 
term because it's either the twelfth and 
we only are interested in z to the tenth 
and so anything that z to the twelfth 
multiples by is going to be bigger than z 
to the tenth and we don't we don't even 
need to carry that term. 
So this is exactly an equality. 
We just keep the ones that could possibly 
contribute to the coefficient of z^10th. 
So now the exponentials are gone, and we 
have these lists of polynomials. 
But, I, if you do the same thing, with 
the 1 over 1 - z, then we only need to 
keep the first 10 terms of that one. 
and then for each one of these, you cross 
multiple each one of these, I really only 
need to keep the one were 
You picked like z^8/8 and it multiplies 
by 1 and all the other terms so that's 
the z^8/8. 
So multiply any one of those others its 
going to get something bigger than z^10. 
It can't contribute a coefficient of 
z^10. 
So now, we just have product of Two term. 
The focus on z ^ 10 is easy because the 
cross-multiply is one contribution from 
each one. 
Then it's just 1 - 1/6 - 1/7 and so 
forth. 
So the minus 6, 1/6 comes from z ^ 6 / 6 
* z ^ 4 and now 1 / 7 is z ^ 7 / 7 * z ^ 
3 and so forth. 
So 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, for a particular 
problem. 
As an application we're going to consider 
a problem known as the 100 prisoners 
problem. 
this was actually a Google interview 
question for a while, so the idea is you 
have a, its a story where you have 100 
prisoners each that each have a a unique 
identity card. 
So the prisoners are numbered from one to 
100 and each have a card. 
now they have been sentenced to death 
because they're on the wrong side of a 
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 doors. 
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 setup. 
Now the prisoners, one at a time, are 
allowed to go into The room has a 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 open, can look at 50 
drawers but not all of them. 
And so when the prisoner comes out, they 
have to announce whether they, 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 any one of them doesn't, then they're 
all executed. 
Okay. 
1 prisoner can't find the number they're 
all executed. 
So now one of the prisoners is a 
mathemetician, prisoner A, who 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 ^ -100. 
And that is an exceedingly unbelievably 
small number, we'd have no chance. 
If fact, it won't talk too long before 
somebody can't find their own number. 
The, ther'es another prisoner who knows 
some analytical combinatorics and, and he 
said, I thik I have an idea I know a 
strategy where at least we ahve a 30% 
chance of success. 
So that's the google interview question 
of what's the strategy. 
so really what prisoner A was saying was 
that his strategy was going to be pick 
drawers at random. 
and obviously that's not the best 
strategy. 
So, what's prisoner B 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 should He knows 
what his number is, say it's number 5, so 
he should open the drawer that has number 
5 and then use that number to decide what 
drawer to open next. 
And then just keep going. 
now is going to continue until he finds 
the drawer that contains his own ID. 
and so, that's going to be the strategy. 
Well also, he has to stop if he gets to 
50 drawers. 
So if you think about that when does the 
strategy and when does it fail? Well it's 
going to succeed. 
If the permutation that represents the 
cards in the drawers 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 in E^(z/1+z/2+...+z/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-(H100-H50), which is about 1/ln2.31. 
That's a solution to the 100 prisoners 
problem and an application of a study of 
the cycle structure of permutations.