## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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.
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.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required