Today, our topic is Permutations, another 
basic combinatorial structure that we 
study because it has numerous 
applications in analysis of algorithms. 
Again, continuing the orientation that we 
introduced in the last lecture, we're on 
the second part of the class where we're 
surveying fundamental combinatorial 
classes and mathematical techniques that 
we covered in the first half of the 
class. 
Primarily analytic combinatorics to study 
properties of these classes. 
Last time we studied trees, mostly, from 
the standpoint as unlabeled structures 
which we analyze with ordinary generating 
functions. 
This time we're going to switch to 
labeled structure as permutations. 
in exponential generating functions. 
again there's many more, examples i the 
book then you can possibly cover in 
lectures. 
what we try to do in lectures is cover 
some of the interesting ones then you can 
read more, in For the extend your 
knowledge by studying from the book. 
You couldn't possibly cover, all the 
examples that are in the book in 
lectures. 
so let's look at the basic properties of 
permutations. 
We talked about permuations before as an 
example in introducting labeled 
strucutres in analytical combinatorics. 
So here's just 1 colorful metaphor to 
describe permutations that we've 
discussed. 
You have a group of N students that go to 
a party and they maybe become inebriated 
that when the party is over they each 
wind up in a random room. 
So if the students have numbers one 
through sixteen, and the rooms have 
numbers one through sixteen. 
Then, what you have if you arrange in 
order by student. 
What you have is a random ordering of the 
numbers one through sixteen, or a 
permutation. 
so in, we looked at those, from the 
standpoint of analytic combinatorics as a 
sequence of labeled atoms. 
where each possible ordering is 
different. 
So there's six permutations of three 
Elements in 24 permutations of 4, and so 
forth. 
And so there's N factorial permutations 
of N elements. 
And from the point of view of generating 
functions, the exponential generating 
functions for permutations it kind of 
sequences in factorial. 
And we have a normalizing factor, N 
factorial. 
So, those cancel out and it's the 
exponential generating. 
Function for permutations, is sum of z^n 
1/1-z. And this is just a quick review of 
what we talked about, in the analytic 
combinatorics lecture. 
so now, this, many, many interesting 
properties of permutations that have been 
studied. 
so, one thing that's often of interest is 
what's called the inverse, of a 
permutation. 
Another way to think of a permutation is 
as a mapping of the numbers from one 
through n, the set of numbers from 1 
through n, to itself. 
so our student to room then, that's a 
mapping from one to nine, two to 12 and 
so forth where all the numbers from one 
through n appear in the mapping. 
Thing. 
So there's a concept known as the inverse 
of a permutation. 
which is just the inverse of that mapping 
and one way to look at that is to 
rearrange the permutation table. 
so that it's in order by the rooms and 
then, flip it. 
so permutation maps students to room, the 
inverse of that permutation maps rooms to 
students. 
So, it says that student room 1 has 
student 7 in it, room 2 has student 13 in 
it and so forth. 
where as the permutation told us which 
student was in which room. 
and there's lots of direct a- a- 
applications of inverse. 
how do you compute the inverse? it's a 
very simple process. 
here's the code for it and the code is 
only slightly complicated because 
Nowadays arrays in Java, C, and other 
languages are uh,zero-based, the first 
thing's at 0, and we've been using 
permutations the first thing's at 1 but 
let's look at an example and then we'll 
go back to the code. 
So if we had this permutation shown on 
the right where 1 maps to 8, 2 maps to 1 
and so forth. 
we want to compute the inverse of that 
permutation. 
The process is very simple we start out 
with an, an empty array. 
and the first thing you do, to get the 
inverse, one goes to eight so in the 
inverse, eight is going to have to go to 
one. 
So we simply put a one in position eight 
in the inverse. 
And then we just move from left from 
right we put a 2 in position 1, 3 in 
position 3. 
Four in position seven. 
Five in position six. 
Six in position two. 
Seven in nine. 
Eight in four. 
And nine in five and so forth. 
so since we know that, each thing appears 
only once. 
There's no collision in this process, and 
simply one pass through the array is 
showed in the for loop in the code at 
left. 
you can fill in the inverse in this case, 
the array. 
Be and since the arrays are 0 based we 
have to subtract 1 from the permutation 
number. 
so when 2 goes into position 1 it goes 
into the first position in the array 
which is position 0, so we subtract 1. 
and then we're using index i that goes 
from 0 to n -1 so we really need to stick 
with the convention we've been using with 
1 through n we just add 1 to i. 
So that's an easy computation one pass 
through we can compute the inverse of a 
computation. 
and here's a, a sample application, one 
of the simplest cipher mechanisms is 
simply to, it's called a substitution 
cipher, is first generate a random 
permutation of the letters A through z 
and in this case we use a minus sign for 
a blank. 
we'll talk about generating random 
permutation in a minute. 
and then we use that mapping to encrypt a 
message. 
So if the message what's just called the 
plain text, plain text, is attack at 
dawn. 
Then the random permutation tells us that 
A should map to W. 
T to P, T to P again, A to W again. 
C to L and so forth. 
And that gives us a cypher text, and it's 
encrypted we can send that cypher text 
and an eaves-dropper. 
couldn't figure out what the plain text 
is, without knowing the random 
permeation. 
So, that's a simple sipher system and 
now, but the receiver of the message, in 
order to be able to understand what the 
message says. 
Has to have the inverse of that 
permutation. 
so that's a key that's transmitted in, or 
generated in some other way. 
But in order to decrypt, we need the 
inverse of the permutation. 
and the inverse will tell us that W is 
supposed to go to A. 
P is supposed to go to T and so forth And 
so that just a computing the inverse as 
in the previous slide. 
and that gives a mechanism for converting 
the cipher text back to the plain text. 
So that's a very simple application of 
the inverse of a permutation. 
now actually this type of cypher system 
is not so often used nowadays because it 
always maps each character to the same 
character. 
And so actually an eavesdropper, can 
figure out by the frequency of occurrence 
of the letters which, which letter codes 
to which letter. 
and actually not too difficult to solve a 
cipher system built this way from that 
frequency frequency analysis. 
but it's useful as maybe a piece of a 
cipher system. 
sometimes we work with what's called the 
lattice representation of a permutation. 
We simply make an end-by-end matrix. 
and down at the bottom is the 
permutation. 
so it makes a, a, example for a mutation. 
And all we do is for each entry in the 
permutation, we put a block in the 
corresponding row. 
So the first column corresponds to ninth 
we put a block in row nine. 
Second column, 12. 
Put a black in red 12. 
11-10. 
then 5, and then so forth. 
So we have N blocks marked in that 
permutation. 
In that lattice in it is a direct 
correspondence to that permutation. 
and then, what's interesting and it 
doesnt take too much thought to convince 
yourself this works, is if you look on 
the columns that are marked one by one 
The first column is marked as 7, the 
second one is 13 and so forth. 
And if you just read off the columns that 
marked, what you get is the inverse of 
the permutation. 
so [COUGH] the, in the permutation, 1 
maps to 9. 
And then in the incerse, 9 maps to 1. 
so that block is interpreted both ways 
and, in fact, if you take the transpose 
of the representation of the permutation 
in terms of the lattice, you get 
representation of the inverse. 
so that's sometimes a, a useful way to or 
interesting way to look at permutations. 
and re- remember when we talked about 
introduced analytic combinatorics, we 
talked about the cycle representation of 
a permutation. 
so if Student 4 was at room. 
In room, [COUGH], in room 10, in, goes to 
room 10, he's going to find student 6 
there, student 6 is going to go to room 
15 and so forth. 
eventually Student 4 will find his room 
that way. 
so, doing that for every position, in the 
permeation, we, it's, we saw that, 
there's a set of cycles that's equivolent 
to any given permeation. 
[COUGH] and, with that set of cycles 
representation, we're able to analyze 
interesting properties of permutation. 
I mention that 'cuz we're going to extend 
some of that analysis later on. 
and [COUGH], then the tool, the main tool 
that we use to study permutations when 
introduce it for analytic combinatorics. 
and today the starting is the symbolic 
method for labeled classes. 
we had a, number of common notarial 
constructions. 
Other natural ways to define sets of 
label objects including permutations with 
restrictions on cycle lengths and other 
properties. 
And the symbolic method is a set of 
transfer theorems, or a, a transfer 
theorem, that defines a correspondence 
between a construction and operation on a 
generating function so when we build 
constructions, we get generating 
functions. 
so for example The, one way to count 
permutations using the symbolic method, 
define the class of all permutations and 
the exponential generating function, 
which is each permutation, Z to the size 
divided by size factorial, which is 
equivalent to sum of N of the number of 
permutations of size N, z/N factorial. 
The combinatorial construction, that 
creates permutations. 
So is that a permutations either empty or 
it's a star product of an atom and a 
permutation. 
And that transfers immdediately to the 
OGF equation. 
1+zP(z). 
and that has a solution, 1/1-z). 
and then the co-efficient is z/N, and 
that is N factorial. 
So, a fine application of the study of 
permutation is sorting algorithms. 
chapter 2 of our algorithm book has 
numerous classic sorting out algorithms. 
And, these things are very efficient, 
well studied, widely used and extremely 
useful. 
And one reason that we've been able to 
develop them to the point where they're 
so efficient is that we have mathematical 
models based on permutations that help us 
understand them. 
And we saw examples of that in the very 
first lecture and second lecture when we 
talked about the analysis of quick sort 
and merge sort. 
and the key concept as we saw, was we 
need a model for the input to a sorting 
algorithm. 
and 1 thing to start with is to say that 
the inputs are randomly ordered. 
They perform, they represent a random 
permutation. 
the question is, is that a realistic 
model? and the answer is, that absolutely 
it's a realistic model. 
if we just apply a random permutation to 
the input before the sort. 
so the input might not be in random. 
In the motor in this case it's in reverse 
order but if we randomly permute it then 
we absolutely have a situation where 
we're sorting a set of items that are 
random permutations so the model is 
exact. 
So if we study properties of random 
permutations then we get properties of 
our sorting algorithms. 
And that's what we're going to be doing. 
that's what we did for quick sort and 
we'll do for several other sorting 
algorithms today. 
so in order to do this though, you need 
to be able to generate a random 
permutation properly. 
and actually at the beginning people 
would get this wrong. 
They'd generate things that looked like 
they were randomly permuted. 
But actually did not generate each 
permutation with equal likelihood. 
so nowadays,uh, we use a method 
articulated, by Knuth and probably 
earlier. 
And just go from left to right. 
And exchange each entry with a random 
entry to its right. 
so there's a 2 liner, a 4 liner, a 5 
liner to a generate a random permutation, 
I goes from 0 to N we generate a, index r 
that is somewhere between i and n-1 
between the current position and the end 
of the array and then exchange the 
element at position i with element at 
position r So again if we start with this 
input maybe that's in reverse order. 
and first case generates an index that 
points to N in exchange to T and N. 
And next, next time were going to 
exchange S with L, and then T with R, and 
then R with P, and so forth. so each time 
the element that gets picked at random 
from the ones that had not been chosen 
yet. 
and we continue in that process we get a 
random permutation of the input arrays. 
Or if we just want to generate a random 
permutation just start with 1 through N 
as the input and you get out a random 
permutation. 
In this process generates all 
permutations with equal likelihood and 
then that's easy to see. 
the first entry is equally likely to be 
anyone of the N entries, where picking 
any value from 0 to N-1 at random, we 
could get any one of them, so there's N 
possibility for the first entry. 
Similarly, there's N-1 possibility for 
the second entry, and so forth. 
So there's a total of N factorial 
different, choices, different 
permutations that are possible to be 
generated. 
And they're all equally likely. 
That's the basic properties of 
permutations. 
And next, we'll going into looking at 
analyzing some of them.