So let's look at the basic properties of permutations.

And we talked about permutations before,

as an example when introducing labeled structures and analytic combinatorics.

So here's just one colorful metaphor to describe permutations that we discussed.

You have a group of N students, and they go to a party.

And they maybe become inebriated, that when the party's over,

they each wind up in a random room.

So you have the students have numbers 1 through 16 and

the rooms have numbers 1 through 16.

Then what you have if you arrange in order by student,

what you have is a random ordering of the numbers 1 through 16, or a permutation.

So 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, and

24 permutations of four, 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,

the counting sequence is N 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 to the n of 1 over 1-Z.

And this is just a quick review of what we talked about in

the analytic combinatorics lecture.

So now, there's 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 set of numbers from 1 through N to itself.

So our student to room, that's a mapping from 1 to 9, 2 to 12, and so

forth, where all the numbers from 1 through N appear in the mapping.

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 rooms,

the inverse of that permutation maps rooms to students.

So it says that in room 1 has student 7 in it,

room 2 has student 13 in it, and so forth.

Whereas the permutation told us which student was in which room.

And there's lots of direct 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 and C and other languages are zero-based.

The first thing's at zero, and

we've been using permutations the first things at one.

But let's look at an example and then we'll go back to the code.

So if we have 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 empty array, and

the first thing we do to get the inverse 1 goes to 8.

So in the inverse, 8 is going to have to go to 1.

So we simply put a 1 in position 8 in the inverse.

And then we just move from left to right, we put a 2 in position 1,

3 in position 3, 4 in position 7, 5 in position 6,

6 in position 2, 7 in 9, 8 in 4, and 9 in 5, and so forth.

So since we know that each thing appears only once,

there's no collision in this process.

In simply one pass through the array, as shown in the for

loop in the code at left, we can fill in the inverse, in this case, the array B.

And since the arrays are zero-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 one.

And then we're using index i that goes from 0 to N-1, so

we're ready to stick with the convention that 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 permutation.

And here's a sample application, one of the simplest cipher

mechanisms is simply, 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.

And we'll talk about generating random permutation in a minute.

And then we use that mapping to encrypt a message.

So if the message, which is called the plaintext, 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 the ciphertext, and it's encrypted.

We can send that ciphertext, and an eavesdropper couldn't figure out

what the plaintext is without knowing the random permutation.

So that's a simple cipher 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, and they're generated in some other way.

But in order to decrypt, we need the inverse of the permutation.