26 CHAPTER 3

and then we can rearrange the lines to give

a → b

(g ◦ h)

−1

: b → c

c → a.

EXERCISE: Compare (h ◦ g)

−1

and g

−1

◦ h

−1

and conﬁrm that

they are equal.

SOLUTION: Both (h ◦ g)

−1

and g

−1

◦ h

−1

are equal to

a → c

b → a

c → b.

The permutations of a given set A are always a group,

2

using

composition to combine pairs of elements. We use the symbol

A

to denote this group, read “Sigma sub A.” If A has more

than two elements, then the composition in

A

does not obey the

commutative law.

EXERCISE: If A has n elements, explain why

A

has n!

elements.

Cycles

One of the niftiest elementary things about a permutation is called

its cycle decomposition. In o rder to give you an interesting example,

we start with a permutation of the ﬁrst 10 letters of the alphabet,

{a, b, c, d, e, f , g , h, i, j}. We write the permutation vertically rather

2

We have not yet checked the associative axiom. If h, g,andk are permutations of A,we

must verify that h ◦ (g ◦ k) = (h ◦ g) ◦ k. This follows from the fact that h, g,andk are

functions from A to A.

PERMUTATIONS 27

than horizontally, to take up less space. Here is our permutation:

abcdef ghi j

↓↓↓↓↓↓↓↓↓↓

beaihdcf jg

.

We start with the letter a, and play the following game. The letter

a gets mapped to the letter b, w hich in turn gets mapped to the

letter e, which in turn gets mapped to the letter h,whichinturn

gets mapped to the letter f , which in turn gets mapped to the letter

d, which in turn gets mapped to the letter i, which in turn gets

mapped to the letter j, which in turn gets mapped to the letter g,

whichinturngetsmappedtotheletterc, which in turn gets

mapped to the letter a. If you think about it for a moment, you

will realize that we had to come back to a eventually.

EXERCISE: Convince yourself that we had to return to the

letter a eventually.

SOLUTION: Because there are only 10 letters involved, the

ﬁrst thing to notice is that some letter has to show up on the

list twice if we play the game long enough. Call the ﬁrst letter

to show up twice x, and suppose that x is not the letter a.We

get a picture like this one:

a → b →···→y → x →···→z → x.Becausethe

permutation is one-to-one, we are forced to conclude that

the letter before each of the two x’s is the same as well,

contradicting the assumption that x is the ﬁrst letter to show

up twice. The only way out is if a is the ﬁrst letter to appear

twice.

Put the whole list, starting with a, on one long line:

a → b → e → h → f → d → i → j → g → c → a.

This is called a cycle, and it is customary (though confusing at ﬁrst)

to write it as (abehfdijgc). Notice that we omit the second a.

Start Free Trial

No credit card required