S2, C2: Permutations

Question 1

What is a permutation?

Answer 1

A bijective function f: X -> X denoted Sn.

Question 2

The number of permutations in Sn is…

Answer 2

n!

Question 3

Define disjoint

Answer 3

A set of cycles is disjoint if no element appears in more than one of them.

Question 4

Define Cycle Decomposition

Answer 4

a cycle decomposition of a permutation a is an expression of a as a product of disjoint cycles.

Question 5

What is a (adjacent) transposition?

Answer 5

a cycle of length 2

a adjacent transposition is one of the form (i i+1), e.g. (3 4).

Question 6

What is parity?

Answer 6

oddness or evenness

Question 7

When is a permutation even/odd?

Answer 7

It’s said to be even if it can be written as a product of an even number of transpositions.

• id is even.
• any transposition is odd.
• cycles of even length are odd and vice versa.

Question 8

What is the sign of a permutation, written sgn(a)?

Answer 8

+1 if a is even and -1 if a is odd.

Question 9

What is the order of a permutation, a?

Answer 9

the least positive integer m such that
a^m = id.
The lcm of the the length of the disjoint cycles.