1
00:00:01,364 --> 00:00:05,409
Okay. 
Next, we're going to, expand the kind of 

2
00:00:05,409 --> 00:00:12,090
analysis that we did when we introduced 
permutations, in, this lecture. 

3
00:00:12,090 --> 00:00:18,302
Look at permutations such as cycles with 
restrictions on the cycle length. 

4
00:00:18,302 --> 00:00:25,997
I recall that we study this when looking 
at introducing analytic common torts, 

5
00:00:25,997 --> 00:00:31,972
with the following kind of construction. 
A permutation is a set of cycles. 

6
00:00:31,972 --> 00:00:37,658
then from the symbolic transfer theorem 
for labeled objects. 

7
00:00:37,658 --> 00:00:44,774
that means that the generating functions 
satisfies for set, it's exponential, for 

8
00:00:44,774 --> 00:00:47,274
cycle it's natural log. 
So P(z)=e^ln1/1-z), 

9
00:00:47,274 --> 00:00:53,846
which is 1/1-z. 
So therefore, the counting sequence is 

10
00:00:53,846 --> 00:01:00,218
N![z^N], that which is N!. 
and if you want to extend that to same 

11
00:01:00,218 --> 00:01:04,604
analysis to count the number of de-, 
derangements that the pigmentation, we 

12
00:01:04,604 --> 00:01:12,654
know singleton cycles, then we just 
restrict the length of the cycle'd be 

13
00:01:12,654 --> 00:01:21,005
bigger then 1, which corresponds to, 
leaving off the, the z, in natural log of 

14
00:01:21,005 --> 00:01:27,242
1/1-z, so natural log 1/1-z-z, is 
(z^2)/2+z and so forth. 

15
00:01:27,242 --> 00:01:35,267
in or in other words, look at it's just 
natural (ln1/1-z-z), and then, that's 

16
00:01:35,267 --> 00:01:40,811
e^-z/1-z. 
so the coefficient of z to the N that is 

17
00:01:40,811 --> 00:01:47,522
a convolution, which is (-1)^k/k!, which 
is asymptotic to 1/e. 

18
00:01:47,522 --> 00:01:54,456
it's and then we did the generalized 
derangements, if we restrict the no show 

19
00:01:54,456 --> 00:02:00,945
short cycles of length <= parameter M. 
And the it's just a straight 

20
00:02:00,945 --> 00:02:05,600
generalization of the argument for 
derangements. 

21
00:02:05,600 --> 00:02:10,241
Where now it's e, and then we started 
z^n+1/n+1. 

22
00:02:10,241 --> 00:02:17,041
or that's ln1/1-z-z all the ones <= to M. 
which is e^-z- and so forth /1-z. 

23
00:02:19,841 --> 00:02:27,341
and then we showed an analytic transfer 
theorem that tell us that the asymptotics 

24
00:02:27,341 --> 00:02:35,022
of that is, N!/e^HM. so, that's a review 
of what we talked about in terms of 

25
00:02:35,022 --> 00:02:39,996
permutations with cycle length 
restrictions when introducing analytic 

26
00:02:39,996 --> 00:02:43,865
combinatorics. 
And now we'll look at another problem of 

27
00:02:43,865 --> 00:02:47,112
that flavor. 
and that's involutions. 

28
00:02:47,112 --> 00:02:53,092
an involution is the permutation where 
all the cycles have to be short. 

29
00:02:53,092 --> 00:02:58,272
So they either have to be length 1 or 2, 
and then involution. 

30
00:02:58,272 --> 00:03:02,296
So out of the, 24 permutations of, of 
length 4. 

31
00:03:02,296 --> 00:03:07,310
only 10 of them have cycles of length or 
of length 1 or 2. 

32
00:03:07,310 --> 00:03:14,001
the others either have either, one cycle 
of length 3 or one cycle of length 4. 

33
00:03:14,001 --> 00:03:18,432
Simiarly there are only 4 of the 
permutations of size 3. 

34
00:03:18,432 --> 00:03:21,322
that don't have any 3 cycles and so 
forth. 

35
00:03:21,322 --> 00:03:26,677
so the question we're going to want to 
take a look at is how many involutions 

36
00:03:26,677 --> 00:03:32,067
there are? involutions are actually 
interesting combanitorial objects with 

37
00:03:32,067 --> 00:03:36,152
lots of applications. 
One way to see it is to think again about 

38
00:03:36,152 --> 00:03:39,342
inverses. 
Remember a permutation is a mapping, if 

39
00:03:39,342 --> 00:03:44,222
we look at the permutations of mapping 
the numbers 1 through N to itself, then 

40
00:03:44,222 --> 00:03:49,412
the N is the inverse to that mapping so 
if we think of students in rooms and sort 

41
00:03:49,412 --> 00:03:52,302
by room and flip the rows, we get the 
inverse. 

42
00:03:52,302 --> 00:03:59,049
What's the inverse of an involution? I've 
it's in if you take an involution and 

43
00:03:59,049 --> 00:04:04,855
compute the inverse by again, sorting by 
the, bottom. 

44
00:04:04,855 --> 00:04:10,056
Sorting in columns so it's really by the 
bottom row. 

45
00:04:10,056 --> 00:04:16,205
And then flip them. 
you see immediately that you get back, 

46
00:04:16,205 --> 00:04:20,654
the involution. 
So what's the inverse of an involution? 

47
00:04:20,654 --> 00:04:24,007
It's itself. 
And, if you think about the cycle 

48
00:04:24,007 --> 00:04:29,815
representation, taking the mapping and 
the cycle representation is just moving 

49
00:04:29,815 --> 00:04:33,960
one step in the cycle. 
So if you knew of one step, if have a two 

50
00:04:33,960 --> 00:04:38,533
cycle you move one step and then another 
step you go back to where you were. 

51
00:04:38,533 --> 00:04:43,614
If you have a one cycle, you just stay 
you were, so always with two steps you're 

52
00:04:43,614 --> 00:04:48,742
going to get back to the same place 
SO that's why evolutions are significant. 

53
00:04:48,742 --> 00:04:54,993
in the significance of, so in the lattice 
representation the 1 cycles correspond to 

54
00:04:54,993 --> 00:05:01,015
elements that are on the diagonal and 
then the 2 cycles have to be symmetric. 

55
00:05:01,015 --> 00:05:06,108
1 goes to 9, 9 goes to 1. 
and if you transpose it, you get the same 

56
00:05:06,108 --> 00:05:09,600
thing back. 
so involution is it's own inverse. 

57
00:05:09,600 --> 00:05:15,243
and it, it's you see that from the latest 
representation immediately. 

58
00:05:15,243 --> 00:05:20,542
and in terms of applications there's the 
idea of a reciprocal cipher. 

59
00:05:20,542 --> 00:05:26,737
so if you use an involution then what you 
can do is encrypt and decrypt with the 

60
00:05:26,737 --> 00:05:30,844
same machine. 
And actually a famous example of that is 

61
00:05:30,844 --> 00:05:36,453
the Enig machine, Enigma Machine that was 
used by the Germans in World War II. 

62
00:05:36,453 --> 00:05:43,617
one of it's components was an involution. 
so the idea is you have your, our letters 

63
00:05:43,617 --> 00:05:50,222
from A to Z and minus are black again. 
if the permutation that we used to 

64
00:05:50,222 --> 00:05:55,962
encrypt is an involution then we don't 
need to computer the inverse. 

65
00:05:55,962 --> 00:06:01,722
The involution is its own inverse. 
SO we don't need a separate. 

66
00:06:01,722 --> 00:06:06,839
A table to decrypt. 
If we have our plain text and then we get 

67
00:06:06,839 --> 00:06:13,971
the cipher text A goes to D, and so forth 
then do decrypt, we use the same [COUGH] 

68
00:06:13,971 --> 00:06:18,172
involution or permutation which is an 
involution. 

69
00:06:18,172 --> 00:06:23,377
and that same thing says D goes to A, K 
goes to T, and so forth. 

70
00:06:23,377 --> 00:06:28,817
so, involution permutation has it's own, 
it's own inverse. 

71
00:06:28,817 --> 00:06:35,712
and, again, it's still susceptible to the 
character frequency a,attack. 

72
00:06:35,712 --> 00:06:41,249
But it's proven useful as a component in 
a cipher machine, because it can greatly 

73
00:06:41,249 --> 00:06:46,367
multiply the number of possibilities that 
an eavesdropper has to consider and 

74
00:06:46,367 --> 00:06:51,564
that's how it was used in the enigma. 
So, for example, if you want to know how 

75
00:06:51,564 --> 00:06:57,108
many enigmas, different enigma settings 
you have Fine then you have to know 

76
00:06:57,108 --> 00:07:03,404
something about enumerating involutions. 
and most they, from Australia about the 

77
00:07:03,404 --> 00:07:07,848
cryptonalysis of the enigma involving 
Alan Turing and so forth. 

78
00:07:07,848 --> 00:07:13,207
And if you don't know that story, 
definitely worth your while to look it up 

79
00:07:13,207 --> 00:07:17,564
and read about it. 
So, as a warmup, let's take a look at the 

80
00:07:17,564 --> 00:07:22,019
number of permutatoins that are composed 
entirely of two cycles. 

81
00:07:22,019 --> 00:07:27,055
And so, there's only one permutation size 
two that solves two cycles. 

82
00:07:27,055 --> 00:07:32,422
There's three different of size three 
that are all three cycles and so forth. 

83
00:07:32,422 --> 00:07:36,192
and actually an example of this is called 
rot 13. 

84
00:07:36,192 --> 00:07:39,482
So it's the, the world's weakest crypto 
system. 

85
00:07:39,482 --> 00:07:43,860
Where we just take the letters and rotate 
them 13 positions. 

86
00:07:43,860 --> 00:07:48,242
So A goes to N, N goes to A, B goes to O, 
O goes to B and so forth. 

87
00:07:48,242 --> 00:07:52,368
So forth. 
and, you can, read about this one on the 

88
00:07:52,368 --> 00:07:56,122
web. 
It's hacker's delight because anyone, 

89
00:07:56,122 --> 00:08:00,419
encode or decode and people get so they 
read in this and so forth. 

90
00:08:00,419 --> 00:08:06,680
So it's a very, light crypto system that 
hackers use, To just lightly, to put 

91
00:08:06,680 --> 00:08:11,316
stuff out on the web, that maybe's 
inappropriate content. 

92
00:08:11,316 --> 00:08:17,904
but you have to be at least able to 
decript in this way, and nobody get 

93
00:08:17,904 --> 00:08:21,486
offended if they ran across it 
accidentally. 

94
00:08:21,486 --> 00:08:29,587
so again, since it's 2 cycles, it's a 
reciprocal cipher, so You, you, just use 

95
00:08:29,587 --> 00:08:36,962
the same table to decrypt and encrypt. 
so what's, how many permutations or 

96
00:08:36,962 --> 00:08:44,462
controls entirely of two cycles? Well, a, 
a, permutation, we'll call it r, is a, 

97
00:08:44,462 --> 00:08:50,837
it's just a set of two cycles. 
2 cycles is e^z^2/2, so the equation is 

98
00:08:50,837 --> 00:08:55,349
e^z^2/2. 
And so all we want is the coefficient of 

99
00:08:55,349 --> 00:08:59,945
N factorial times the coefficient of Z^n 
in that. 

100
00:08:59,945 --> 00:09:06,169
So that's going to be Z^2 over 2. 
So we've go the Z^2, so it's N over 2 

101
00:09:06,169 --> 00:09:13,858
factorial, and that's the equation, and 
we can do the asymptotics from Sterling's 

102
00:09:13,858 --> 00:09:18,402
approximation to get the number of two 
cycles. 

103
00:09:18,402 --> 00:09:24,162
So, very simple and straightforward with 
basic, electronic torques and 

104
00:09:24,162 --> 00:09:27,507
asymptotics. 
but what about involutions. 

105
00:09:27,507 --> 00:09:34,642
well the construction is pretty simillar. 
it's it's like a one cycle installed with 

106
00:09:34,642 --> 00:09:38,862
a set of two cycles. 
So they're just permutations where all 

107
00:09:38,862 --> 00:09:47,261
the cycles are length 1 or 2. 
so that immediately goes to e, e^z+z^2/2, 

108
00:09:47,261 --> 00:09:55,032
so cycle 1, z, cycle 2, z, and then a set 
of those is e^z+c^2/. 

109
00:09:55,032 --> 00:10:01,978
First one z to z second one z square over 
two so now we want to extract the 

110
00:10:01,978 --> 00:10:08,463
coefficient so whats n factorial 
coefficients of z to the n in that 

111
00:10:08,463 --> 00:10:13,220
function. 
well that, that gets to be a discreet sum 

112
00:10:13,220 --> 00:10:17,328
that is maybe not so easy to analyze. 
N!/k!^2k(N-2k)!. 

113
00:10:21,006 --> 00:10:27,315
So it's a convolution of a term like the 
one we had for just two cycles and then 

114
00:10:27,315 --> 00:10:30,957
1/N!. 
And that's easy to verify. 

115
00:10:30,957 --> 00:10:36,032
So the aymptotics of that, is, a bit more 
complicated. 

116
00:10:36,032 --> 00:10:42,432
It's got a square root 2 fourth root of e 
in it and its its defininately, a, 

117
00:10:42,432 --> 00:10:50,007
intricate looking function, and that's 
available, from the Laplace method for 

118
00:10:50,007 --> 00:10:57,032
sums, remember the Laplace method, we 
isolate where, the sum, most weight of 

119
00:10:57,032 --> 00:11:01,832
the sum is. 
and then, estimate with an integral there 

120
00:11:01,832 --> 00:11:06,127
and also bound the tails and so forth. 
and that's done in coming Part 3. 

121
00:11:07,137 --> 00:11:13,582
later on in Part 2, we'll see how to with 
complex asymptotics, directly get that 

122
00:11:13,582 --> 00:11:17,537
answer out. 
so with the analytic combinatorics you 

123
00:11:17,537 --> 00:11:24,178
can directly to results like that. 
although, a The asymptotic's of that is 

124
00:11:24,178 --> 00:11:30,602
is definitely not trivial. 
and then, if we want to generalize you 

125
00:11:30,602 --> 00:11:38,283
know, how about no big cycles where we 
parameterize the cycle length by m same 

126
00:11:38,283 --> 00:11:44,994
way as we did for the derangement's. 
So now the construction is, its a set of 

127
00:11:44,994 --> 00:11:51,680
one cycle, start with a set of two cycles 
and so forth up to a set of m cycles. 

128
00:11:51,680 --> 00:11:58,418
E^z^2+E^2/2 plus out to z^m over M. 
That's direct from the symbolic method. 

129
00:11:58,418 --> 00:12:05,611
the coefficient asymptotics of that one 
is one of the most difficult derivations 

130
00:12:05,611 --> 00:12:12,925
in our analytics cominotorics books. 
but we, we can know the asymptotics of 

131
00:12:12,925 --> 00:12:20,356
that through analytic combinatorics. 
as an example now for some applications, 

132
00:12:20,356 --> 00:12:26,916
you might not need to actually work out 
the full asymptotics, and just as an 

133
00:12:26,916 --> 00:12:31,499
example. 
I want to show an exercise, so, so this 

134
00:12:31,499 --> 00:12:39,353
is the generating function for the number 
of permutations that have no cycles of 

135
00:12:39,353 --> 00:12:45,029
length bigger than 5. 
So let's say we have permutations of 

136
00:12:45,029 --> 00:12:49,862
length 10, we want to know how many of 
those have. 

137
00:12:49,862 --> 00:12:55,551
no cycles of like bigger than 5. 
So the answer to that question is 

138
00:12:55,551 --> 00:13:03,602
coefficient of z^10, in that function. 
So, that's a very specific question, and 

139
00:13:03,602 --> 00:13:10,068
still it's worth while looking at a 
calculation like that, to get some 

140
00:13:10,068 --> 00:13:16,399
facility for types of problems that 
sometimes arise. 

141
00:13:16,399 --> 00:13:27,160
so if we write the generating function in 
say the other form, the alternate form, 

142
00:13:27,160 --> 00:13:32,012
it's a log(1/1-z) - then the bigger 
terms. 

143
00:13:32,012 --> 00:13:37,049
so that's equivalent. 
1 / (1 - z) is the sum of z^k / k. 

144
00:13:37,049 --> 00:13:43,634
and if we subtract that ones bigger than 
six then we get the ones less than or 

145
00:13:43,634 --> 00:13:48,759
equal to five. 
now with that we can e^ ln(1/(1-z)) is, 

146
00:13:48,759 --> 00:13:55,612
is just e ^ (1/(1-z)) and then we have, 
the other times, multiplied out. 

147
00:13:55,612 --> 00:14:05,509
Now the key idea here is that each one of 
those terms, if we use Taylor's theorem 

148
00:14:05,509 --> 00:14:11,667
to expand them, we only need to keep the 
first term. 

149
00:14:11,667 --> 00:14:16,942
e ^ -z ^ 6 / 6 is 1 - z ^ 6 / 6. 
Plus z ^ 12 /, over 

150
00:14:16,942 --> 00:14:23,518
In 2! by 12 but we don't need the next 
term because it's either the twelfth and 

151
00:14:23,518 --> 00:14:29,089
we only are interested in z to the tenth 
and so anything that z to the twelfth 

152
00:14:29,089 --> 00:14:34,938
multiples by is going to be bigger than z 
to the tenth and we don't we don't even 

153
00:14:34,938 --> 00:14:38,575
need to carry that term. 
So this is exactly an equality. 

154
00:14:38,575 --> 00:14:43,918
We just keep the ones that could possibly 
contribute to the coefficient of z^10th. 

155
00:14:43,918 --> 00:14:49,082
So now the exponentials are gone, and we 
have these lists of polynomials. 

156
00:14:49,082 --> 00:14:55,656
But, I, if you do the same thing, with 
the 1 over 1 - z, then we only need to 

157
00:14:55,656 --> 00:15:02,876
keep the first 10 terms of that one. 
and then for each one of these, you cross 

158
00:15:02,876 --> 00:15:09,192
multiple each one of these, I really only 
need to keep the one were 

159
00:15:09,192 --> 00:15:14,002
You picked like z^8/8 and it multiplies 
by 1 and all the other terms so that's 

160
00:15:14,002 --> 00:15:17,147
the z^8/8. 
So multiply any one of those others its 

161
00:15:17,147 --> 00:15:21,882
going to get something bigger than z^10. 
It can't contribute a coefficient of 

162
00:15:21,882 --> 00:15:25,741
z^10. 
So now, we just have product of Two term. 

163
00:15:25,741 --> 00:15:34,436
The focus on z ^ 10 is easy because the 
cross-multiply is one contribution from 

164
00:15:34,436 --> 00:15:39,113
each one. 
Then it's just 1 - 1/6 - 1/7 and so 

165
00:15:39,113 --> 00:15:43,968
forth. 
So the minus 6, 1/6 comes from z ^ 6 / 6 

166
00:15:43,968 --> 00:15:49,082
* z ^ 4 and now 1 / 7 is z ^ 7 / 7 * z ^ 
3 and so forth. 

167
00:15:49,082 --> 00:15:55,389
So look at that derivation you pretty 
much convince yourself you can easily 

168
00:15:55,389 --> 00:16:01,353
convince yourself that that's an 
effective way to calculate a coefficient 

169
00:16:01,353 --> 00:16:04,438
like that for a, for a particular 
problem. 

170
00:16:04,438 --> 00:16:10,053
As an application we're going to consider 
a problem known as the 100 prisoners 

171
00:16:10,053 --> 00:16:14,170
problem. 
this was actually a Google interview 

172
00:16:14,170 --> 00:16:20,583
question for a while, so the idea is you 
have a, its a story where you have 100 

173
00:16:20,583 --> 00:16:24,911
prisoners each that each have a a unique 
identity card. 

174
00:16:24,911 --> 00:16:29,212
So the prisoners are numbered from one to 
100 and each have a card. 

175
00:16:29,212 --> 00:16:34,057
now they have been sentenced to death 
because they're on the wrong side of a 

176
00:16:34,057 --> 00:16:37,392
civil war or whatever but they're given a 
last chance. 

177
00:16:37,392 --> 00:16:42,955
and so the last chance is that The ID 
cards are all collected in this cabinet 

178
00:16:42,955 --> 00:16:48,084
that has 100 numbered doors. 
The cards are collected and shuffled, put 

179
00:16:48,084 --> 00:16:53,450
in random order, and then they're put in 
the drawers, one card per drawer. 

180
00:16:53,450 --> 00:16:57,900
So now that's the setup. 
Now the prisoners, one at a time, are 

181
00:16:57,900 --> 00:17:04,660
allowed to go into The room has a cabinet 
and open a drawer, look at a card and 

182
00:17:04,660 --> 00:17:10,504
then close the drawer, and they get to do 
that for at most 50 drawers. 

183
00:17:10,504 --> 00:17:17,131
so each prisoner can open, can look at 50 
drawers but not all of them. 

184
00:17:17,131 --> 00:17:22,508
And so when the prisoner comes out, they 
have to announce whether they, what 

185
00:17:22,508 --> 00:17:27,935
drawer their number is in, and if all of 
them find their own number, then they 

186
00:17:27,935 --> 00:17:31,711
won't be executed. 
But they have to all find their own 

187
00:17:31,711 --> 00:17:35,146
number. 
If any one of them doesn't, then they're 

188
00:17:35,146 --> 00:17:36,757
all executed. 
Okay. 

189
00:17:36,757 --> 00:17:40,733
1 prisoner can't find the number they're 
all executed. 

190
00:17:40,733 --> 00:17:46,049
So now one of the prisoners is a 
mathemetician, prisoner A, who says,well 

191
00:17:46,049 --> 00:17:51,926
this is hopeless, we're all going to die. 
Because we can each only open 50 drawers 

192
00:17:51,926 --> 00:17:56,682
and they're randomly ordered, so that 
means that we each have. 

193
00:17:56,682 --> 00:18:02,927
Only half, a chance of one half of 
finding our number and there's 100 of us, 

194
00:18:02,927 --> 00:18:07,457
so the chance that we'd all find our 
number is 2 ^ -100. 

195
00:18:07,457 --> 00:18:13,792
And that is an exceedingly unbelievably 
small number, we'd have no chance. 

196
00:18:13,792 --> 00:18:20,342
If fact, it won't talk too long before 
somebody can't find their own number. 

197
00:18:20,342 --> 00:18:25,872
The, ther'es another prisoner who knows 
some analytical combinatorics and, and he 

198
00:18:25,872 --> 00:18:30,837
said, I thik I have an idea I know a 
strategy where at least we ahve a 30% 

199
00:18:30,837 --> 00:18:35,059
chance of success. 
So that's the google interview question 

200
00:18:35,059 --> 00:18:40,629
of what's the strategy. 
so really what prisoner A was saying was 

201
00:18:40,629 --> 00:18:45,418
that his strategy was going to be pick 
drawers at random. 

202
00:18:45,418 --> 00:18:49,422
and obviously that's not the best 
strategy. 

203
00:18:49,422 --> 00:18:56,129
So, what's prisoner B strategy? Well, 
from the context maybe many of you have 

204
00:18:56,129 --> 00:19:00,704
figured it out. 
so the strategy is that each prisoner 

205
00:19:00,704 --> 00:19:05,802
should follow the cycle. 
That is, each prisoner should He knows 

206
00:19:05,802 --> 00:19:11,927
what his number is, say it's number 5, so 
he should open the drawer that has number 

207
00:19:11,927 --> 00:19:16,567
5 and then use that number to decide what 
drawer to open next. 

208
00:19:16,567 --> 00:19:22,416
And then just keep going. 
now is going to continue until he finds 

209
00:19:22,416 --> 00:19:28,837
the drawer that contains his own ID. 
and so, that's going to be the strategy. 

210
00:19:28,837 --> 00:19:32,707
Well also, he has to stop if he gets to 
50 drawers. 

211
00:19:32,707 --> 00:19:38,965
So if you think about that when does the 
strategy and when does it fail? Well it's 

212
00:19:38,965 --> 00:19:43,586
going to succeed. 
If the permutation that represents the 

213
00:19:43,586 --> 00:19:49,555
cards in the drawers has no long cycles, 
no cycles of length greater than 50. 

214
00:19:49,555 --> 00:19:54,984
So what's the chance that a random 
permutation has no cycles of length 

215
00:19:54,984 --> 00:20:00,406
greater than 50? Well, it's the 
coefficient in E^(z/1+z/2+...+z/50). 

216
00:20:03,134 --> 00:20:09,813
And that's just a slight generalization 
of the little exercise that we just did. 

217
00:20:09,813 --> 00:20:20,078
to see that, that coefficient is going to 
be 1-(H100-H50), which is about 1/ln2.31. 

218
00:20:20,078 --> 00:20:26,492
That's a solution to the 100 prisoners 
problem and an application of a study of 

219
00:20:26,492 --> 00:20:29,352
the cycle structure of permutations.