## 字幕列表 影片播放

• Suppose you have “N” things.

• A permutation is just a rearrangement of the “N” objects.

• For example, if you have a deck of 52 cards, then all the different outcomes of shuffling

• the deck are the permutations.

• There are “N” factorial ways to permute “N” distinct things.

• If you number the objects from one through “N”, then you can write a permutation

• like this.

• The top row are the numbers ordered one through “N”, and the bottom row are the the numbers

• after the shuffling.

• This notation, while clear, takes up a LOT of space.

• Today, well learn a more compact way to write a permutation: cycle notation.

• The permutations on “N” objects can be made into a group which we call thesymmetric

• group,” and we denote it by S-N.

• Here’s how it works.

• Look at these two permutations on 5 elements.

• Each permutation can be thought of as a function where the number on top is the input, and

• the number on bottom is the output.

• If you think of a permutation as a function, then the group operation is function composition.

• If we call the first permutation F, the second permutation G, and treat them as functions,

• then F times G gives you another permutation.

• You can find the product by plugging in each of the 5 numbers.

• If you plug in 1 you get “F of G of 1”.

• Now G sends 1 to 3, so this equals “F of 3”.

• And F sends 3 to 4, so in the product, 1 goes to 4.

• Next, “F of G of 2” equals “F of 1” which equals 3.

• So in the product, 2 goes to 3.

• If you do this for the remaining numbers, you get the permutation 4-3-2-5-1.

• While this way of writing a permutation is clear, it’s very time consuming.

• For each permutation, you have to write every number

• TWICE!

• Cycle notation allows you to write a permutation on a single line, and often times you end

• up writing fewer than N numbers.

• Let’s now see how to rewrite a permutation using cycle notation.

• Look at this permutation.

• Since the top row is always in order, you can read a permutation aloud by only reading

• the bottom line: 3-5-4-1-2.

• To begin, write down the numbers 1 through 5.

• Well start by picking the number 1.

• Scratch off the number 1 from our list.

• The rule is to scratch out a number the moment it appears in a mapping.

• In this permutation, 1 goes to 3, so we can write an arrow showing that 1 maps to 3.

• You can now scratch out the number 3.

• Next, 3 goes to 4, so write an arrow showing 3 maps to 4, and then scratch out 4 from our

• list.

• And finally, 4 maps back to 1.

• You describe these mappings in cycle notation by leaving out the arrows and writing 1-3-4

• inside parentheses.

• But in your mind, be sure you interpret this as saying 1 maps to 3, 3 maps to 4, and 4

• maps back to 1.

• There are still some numbers in our list, so were not done yet.

• The next number that is not scratched out is 2.

• So write down 2 and mark it off from our list.

• 2 maps to 5, so write an arrow mapping 2 to 5, and then scratch out 5 from the list.

• And 5 maps back to 2, so it wraps around.

• If you leave out the arrows, you get the cycle 2-5.

• At this point there are no other numbers in our list, so were done!

• The cycle decomposition of the permutation is 1-3-4 times 2-5.

• Every number appears in exactly one cycle, and each cycle describes part of the permutation.

• So the permutation 3-5-4-1-2 can be written as a product of two cycles.

• The first cycle has length 3, so we call it a 3-cycle.

• The next cycle has length 2, so we call it a 2-cycle.

• A cycle of length two is also called a “transposition.”

• As you can see, cycle notation is much easier to write.

• But there are more things to learn about cycles, so let’s see another example.

• Look at the permutation 2-4-3-1-5.

• In the first example, we wrote the numbers 1 through five, and then started with 1, but

• 2 maps to 4...

• 4 maps to 1... and 1 maps back to 2…

• This gives us the cycle 2-4-1.

• We can mark off these three numbers from our list.

• Next we pick another number that has not yet appeared in a cycle and repeat the process.

• Let’s pick 3.

• 3 maps to itself, so this gives us a cycle with a single number.

• Scratch off 3.

• And 5 maps to itself as well, this gives us another cycle with a single number.

• We can scratch off 5.

• So this permutation is the product of 3 cycles: a 3-cycle, a 1-cycle and another 1-cycle.

• Here’s another shortcut.

• Whenever you have a 1-cycle, you can go ahead and leave it out.

• This is because 1-cycles do not change any number, so we can safely ignore them.

• This means the permutation can be written simply as the 3-cycle 2-4-1.

• But what if we had started with 4 instead of 2?

• 4 maps to 1...

• 1 maps to 2... and 2 maps back to 4, so this gives us the cycle 4-1-2.

• And as before, 3 maps to 3, and 5 maps to 5, and we leave out the 1-cycles.

• And for completeness, what if you had started with 1?

• 1 maps to 2...

• 2 maps to 4... and 4 maps back to 1, giving us the cycle 1-2-4.

• This is curious.

• In the last example, we got three different answers: 2-4-1...

• 4-1-2… and 1-2-4…

• But these cycles are all the same!

• In each cycle, one maps to two.. two maps to four.. and four maps to one..

• Were just writing the mappings in different orders.

• Here’s how to visualize what’s going on.

• Imagine these numbers are on a circle, with arrows going clockwise.

• We then see that 2 maps to 4...

• 4 maps to 1... and 1 maps to 2.

• If we start at the top, this gives us the cycle 2-4-1.

• Look what happens if we rotate this circle a third of a turn.

• Then we get the cycle 1-2-4.

• And if we rotate another third, we get the cycle 4-1-2.

• This is why theyre called cycles!

• While we write the numbers in a row, in reality they represent a loop of mappings.

• These three cycles all represent the same information.

• A good rule of thumb is to pick the cycle that starts with the smallest number.

• So in this case, we’d write it as 1-2-4.

• Next, let’s talk about the order of the cycles in the decomposition.

• Look at the permutation 3-5-6-4-2-1.

• Let’s write this as cycle notation.

• Starting with one, we see one maps to threethree maps to sixand six maps back to

• one.

• This gives us the three-cycle 1-3-6.

• Notice how I’m checking off the numbers on top once they appear in a cycle.

• Moving on to the next unchecked number we see two goes to five, which goes back to two.

• This gives us the two-cycle 2-5.

• Remember, a two cycle is also called a TRANSPOSITION.

• This leaves only 4.

• Four goes to itself, so we get the one cycle 4.

• So this permutation can be written as the product of three cycles: 1-3-6…

• 2-5… and 4…

• We don’t bother writing a one-cycle, so the permutation is the product of a three-cycle

• and a transposition.

• When you write a permutation as a product of cycles, the order of the cycles does not

• matter.

• So we could write this permutation as a three-cycle times a transposition, or as a transposition

• times a three-cycle.

• This is an important point.

• When you decompose a permutation into a product of cycles, the order of the cycles does not

• matter.

• But why is this?

• Here’s why.

• Each cycle can be thought of as a bunch of functions bundled together.

• And notice that each of the numbers appears in one and only one cycle.

• So when you plug a number into these functions, it will only be affected by one of the cycles.

• It passes through the other cycles unaltered.

• For example, let’s look at a permutation from the symmetric group S-7.

• Well consider the product of the 3-cycle 1-3-7 and the transposition 4-6.

• Notice that the numbers 2 and 5 do not appear anywhere.

• This means they are 1-cycles, and when working with cycles, 1-cycles are invisible.

• Let’s now see what happens to a few numbers.

• If you plug in 1, it passes through the transposition unchanged, because 1 does not appear in the

• 2-cycle.

• When it hits the 3-cycle, 1 is mapped to 3.

• Next, look at the number 2.

• 2 is not in either cycle, so it passes through unchanged.

• If you plug in 6, the transposition maps it to 4, but the 3-cycle has no effect.

• The result would be the same if we changed the order of the cycles.

• And since only one cycle changes any number, the order doesn’t really matter.

• But here’s the important part.

• You can rearrange cycles, but only if no number appears in more than one cycle.

• When you write a permutation as a product of cycles, this isn’t a problem.

• Youre guaranteed each number will only appear in a single cycle.

• But when you multiply two DIFFERENT permutations, this is no longer the case.

• In this situation, you will often find the same number in more than one cycle.

• So you can’t rearrange the cycles.

• The technical way to say this is as follows: if two cycles have no number in common, then

• they commute with one another.

• Let’s see an example.

• Instead of working with a single permutation, let’s multiply two different permutations,

• A and B. First, let’s write these permutations in

• cycle notation.