permutations.pdf

Combinatorics. Tutorial 1:

Permutations

As of late, permutations nd their way into math olympiads more and

more often. The latest example is the Balkan Mathematics Olympiad 2001

where the following problem was suggested.

A cube of dimensions 3 × 3 × 3 is divided into 27 unit cells, each of

dimensions 1 × 1 × 1. One of the cells is empty, and all others are

lled with unit cubes which are, at random, labelled 1,2,...,26.

A legal move consists of a move of any of the unit cubes to its

neighbouring empty cell. Does there exist a nite sequence of

legal moves after which the unit cubes labelled k and 27 − k

exchange their positions for all k = 1 , 2 , ..., 13? (Two cells are

said to be neighbours if they share a common face.)

This tutorial was written in responce to this event.

1 Denitions and Notation

We assume here that the reader is familiar with the concept of composition

of functions f and g , which is denoted here as f g . It is a well-known fact

that if f : A ! B is a function which is both one-to-one and onto then f

is invertible , i.e. there exists a function g : B ! A such that g f = id A

and f g = id B , where id A and id B are the identity mappings of A and B ,

respectively. Note that we assume that in the composition f g the function

g acts rst and f acts second: e.g., ( f g )( b ) = f ( g ( b )). There are, however,

many good books using the alternative convention, so it is always necessary

to check whether a particular author uses one or the other convention.

In what follows we will be concerned with invertible functions from a

nite set to itself. For convenience, we assume that the elements of the set

are the numbers 1 , 2 , . . . , n (the elements of any nite set can be labelled

with the rst few integers, so this does not restrict generality).

Denition 1. Let n be a positive integer. A permutation of degree n is a

function f : { 1 , 2 , . . . , n} ! { 1 , 2 , . . . , n} which is one-to-one and onto.

Since a function is specied if we indicate what the image of each element

is, we can specify a permutation by listing each element together with its

image as follows:

3 · · · · · · n − 1

(1) (2) (3)

· · · · · ·

( n − 1) ( n )

is the permutation of degree 7

which maps 1 to 2, 2 to 5, 3 to 3, 4 to 1, 5 to 7, 6 to 6, and 7 to 4. It is clear

that in the second row of such an array all the numbers of the top row must

appear exactly once, i.e. the second row is just a rearrangement of the top

row.

It is also clear that there are exactly n ! permutations of degree n (if you

want to ll the bottom row of such an array, there are n ways to ll the rst

position, n − 1 ways to ll the second position (since we must not repeat

the rst entry), etc., leading to a total of n ( n − 1) · . . . · 2 · 1 = n ! dierent

possibilities).

1 2 3 4 5 6 7

2 5 3 1 7 6 4

2 Calculations with Permutations

The composition of two permutations of degree n is again a permutation of

degree n (exercise: prove that if f : A ! A and g : A ! A are one-to-one

then f g is one-to-one; prove that if f : A ! A and g : A ! A are onto

then f g is onto).

First of all we practice the use of our symbolism for the calculation of the

composition of two permutations. This is best done with a few examples.

In the sequel, we omit the symbol for function composition ( ), and speak

of the product of two permutations and , meaning the composition

Example 1 . Let

1 2 3 4 5 6 7 8

4 6 1 3 8 5 7 2

1 2 3 4 5 6 7 8

2 4 5 6 1 8 3 7

Then

1 2 3 4 5 6 7 8

4 6 1 3 8 5 7 2

1 2 3 4 5 6 7 8

2 4 5 6 1 8 3 7

1 2 3 4 5 6 7 8

6 3 8 5 4 2 1 7

For example =

1 2 3 4 5 6 7 8

2 4 5 6 1 8 3 7

1 2 3 4 5 6 7 8

4 6 1 3 8 5 7 2

1 2 3 4 5 6 7 8

6 8 2 5 7 1 3 4

Explanation: the calculation of requires us to nd

• the image of 1 when we apply rst , then , (1

7! 2

7! 6, so write

the 6 under the 1),

•

the image of 2 when we apply rst , then , (2

7! 4

7! 3, so write

the 3 under the 2),

•

etc.

The calculation of requires us to nd

•

the image of 1 when we apply rst , then , (1

7! 4

7! 6, so write

the 6 under the 1)

• the image of 1 when we apply rst , then , (2

! 6

! 8, so write

the 8 under the 2)

• etc.

All this is easily done at a glance and can be written down immediately;

BUT be careful to start with the right hand factor again!

Important note 1: the example shows clearly that 6 = ; so we have

to be very careful about the order of the factors in a product of permutations.

Important note 2: But the good news is that the composition of

permutations is associative, i.e., ( ) = ( ) for all permutations , , .

To prove this we have to compute:

[( ) ]( i ) = ( )( ( i )) = ( ( ( i ))) ,

[ ( )]( i ) = (( )( i )) = ( ( ( i ))) .

We see that the right hand sides are the same in both cases, thus the

left hand sides are the same too.

We can also calculate the inverse of a permutation; for example, using

the same as above, we nd

− 1 =

1 2 3 4 5 6 7 8

3 8 4 1 6 2 7 5

Explanation: just read the array for from the bottom up: since (1) = 4,

we must have − 1 (4) = 1, hence write 1 under the 4 in the array for − 1 ,

since (2) = 6, we must have − 1 (6) = 2, hence write 2 under the 6 in the

array for − 1 , etc.

Similarly, we calculate

− 1 =

1 2 3 4 5 6 7 8

5 1 7 2 3 4 8 6

Simple algebra shows that the inverse of a product can be calculated from

the product of the inverses (but note how the order is reversed!):

( ) − 1 = − 1 − 1 .

(To justify this, we need only check if the product of and − 1 − 1 equals

the identity, and this is pure algebra: it follows from the associative law that

( )( − 1 − 1 ) = (( ) − 1 ) − 1 = ( − 1 ) − 1 = − 1 = id.)

Denition 2. The set of all permutations of degree n , with the composi-

tion as the multiplication, is called the symmetric group of degree n , and is

denoted by S n .

3 Cycles

A permutation 2 S n which “cyclically permutes” some of the numbers

1 , . . . , n (and leaves all others xed) is called a cycle .

For example, the permutation =

1 2 3 4 5 6 7

1 5 3 7 4 6 2

is a cycle,

! 5, and each of the other elements

of { 1 , 2 , 3 , 4 , 5 , 6 , 7 } stays unchanged, namely 3

! 4

! 7

! 2

! 6. To see that,

we must of course chase an element around, the nice cyclic structure is not

immediately evident from our notation. We write = (5 4 7 2), meaning

that all numbers not on the list are mapped to themselves, whilst the ones

in the bracket are mapped to the one listed to the right, the rightmost one

going back to the leftmost on the list.

Note: cycle notation is not unique, since there is no beginning or end

to a circle. We can write = (5 4 7 2) and = (2 5 4 7), as well as

= (4 7 2 5) and = (7 2 5 4)—they all denote one and the same cycle.

We say that a cycle is of length k (or a k -cycle) if it involves k numbers.

For example, (3 6 4 9 2) is a 5-cycle, (3 6) is a 2-cycle, (1 3 2) is a 3-

cycle. We note also that the inverse of a cycle is again a cycle. For example

! 3, 6

because we have 5

(1 2 3) − 1 = (1 3 2) (or (3 2 1) if you prefer this). Similarly, (1 2 3 4 5) − 1 =

(1 5 4 3 2). Finding the inverse of a cycle one has to reverse the arrows.

Not all permutations are cycles; for example, the permutation

1 2 3 4 5 6 7 8 9 10 11 12

4 3 2 11 8 9 5 6 7 10 1 12

7! 1, but the other elements are not

all xed (2 goes to 3, for example). However, this permutation —and any

other permutation — can be written as a product of disjoint cycles , simply

by chasing each of the elements. The obvious approach is to visualise what

the permutation does: (draw your picture here!)

7! 4

7! 11

From this it is evident that every permutation can be written as a prod-

uct of disjoint cycles. Moreover, any such representation is unique up to the

order of the factors. We also note that disjoint cycles commute; e.g.

(1 2 3 4)(5 6 7) = (5 6 7)(1 2 3 4) .

But we recall that in general multiplication of permutations is not com-

mutative ; in particular, if we multiply cycles which are not disjoint, we

have to watch their order; for example: (1 2)(1 3) = (1 3 2), whilst

(1 3)(1 2) = (1 2 3), and (1 3 2) 6 = (1 2 3).

It is clear that if is a cycle of length k , then k = id, i.e. if this

permutation is repeated k times, we have the identity permutation. More

generally, we will now dene the order of a permutation, and the decompo-

sition into a product of disjoint cycles will allow us to calculate the order of

any permutation.

Denition 3. Let be a permutation. The smallest positive integer i such

that i = id is called the order of .

Example 2 . The order of the cycle (3 2 6 4 1) is 5, as we noted before.

Example 3 . The order of the permutation = (1 2)(3 4 5) is 2 · 3 = 6.

is not a cycle (we have 1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: