Name: 順列のサイクル記法 - 抽象代数 (Cycle Notation of Permutations - Abstract Algebra)
Uploaded: 2021-01-14T08:50:21.000Z
Duration: 12 min 37 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

程度の副詞

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

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

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

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

Today, we’ll 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 the “symmetric

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

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.

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…

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

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

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

To begin, write down the numbers 1 through 5.

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.

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

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

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

There are still some numbers in our list, so we’re 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 we’re 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.

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

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.

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

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

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

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?

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?

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

It seems you get different answers depending on which number you start with.

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

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

We’re 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.

字幕リスト動画再生

順列のサイクル記法 - 抽象代数 (Cycle Notation of Permutations - Abstract Algebra)

pattern

guarantee

matter

convince