s
Section 5.4 Functions
395
A shorter way to describe the permutation f shown in array form is to use
cycle notation and write f = (1, 2, 3)—understood to mean that f maps each
element listed to the one on its right, the last element listed to the first, and an
element of the domain not listed to itself. Here 1 maps to 2, 2 maps to 3, and 3
maps to 1. The element 4 maps to itself because it does not appear in the cycle.
The cycle (2, 3, 1) also represents f. It says that 2 maps to 3, 3 maps to 1, 1 maps
to 2, and 4 maps to itself, the same information as before. Similarly, (3, 1, 2)
also represents f.
PRaCtiCe 35
a. Let A = 51, 2, 3, 4, 56, and let f [ S A be given in array form by
f = a
1 2 3 4 5
4 2 3 5 1
b
Write f in cycle form.
b. Let A = 51, 2, 3, 4, 56, and let g [ S A be given in cycle form by g = (2, 4, 5, 3). Write g in
array form.
■
If f and g are members of S A for some set A, then g + f [ S A , and the action of g + f on any member of A is determined by applying function f and then
function g. If f and g are cycles, g + f is still computed the same way.
example 39
If A = 51, 2, 3, 46 and f, g [ S A are given by f = (1, 2, 3) and g = (2, 3), then
g + f = (2, 3) + (1, 2, 3). But what does this composition function look like? Let’s
see what happens to element 1 of A. Working from right to left (first f, then g),
1 S 2 under f and then 2 S 3 under g, so 1 S 3 under g + f . If we want to write
g + f as a cycle, we see that it can start with
(1, 3
and we next need to see what happens to 3. Under f, 3 S 1 and then under g,
1 S 1 (because 1 does not appear in the cycle notation for g), so 3 S 1 under
g + f . Thus we can close the above cycle, writing it as (1, 3). But what happens to
2 and 4? If we consider 2, 2 S 3 under f and then 3 S 2 under g, so 2 S 2 under
g + f . Similarly, 4 S 4 under f and 4 S 4 under g, so 4 S 4 under g + f . We conclude that g + f = (1, 3).
In Example 39, if we were to compute f + g = (1, 2, 3) + (2, 3), we would get
(1, 2). (We already know that order is important in function composition.) If, however, f and g are members of S A and f and g are disjoint cycles—the cycles have
no elements in common—then f + g = g + f .
Section 5.4 Functions
395
A shorter way to describe the permutation f shown in array form is to use
cycle notation and write f = (1, 2, 3)—understood to mean that f maps each
element listed to the one on its right, the last element listed to the first, and an
element of the domain not listed to itself. Here 1 maps to 2, 2 maps to 3, and 3
maps to 1. The element 4 maps to itself because it does not appear in the cycle.
The cycle (2, 3, 1) also represents f. It says that 2 maps to 3, 3 maps to 1, 1 maps
to 2, and 4 maps to itself, the same information as before. Similarly, (3, 1, 2)
also represents f.
PRaCtiCe 35
a. Let A = 51, 2, 3, 4, 56, and let f [ S A be given in array form by
f = a
1 2 3 4 5
4 2 3 5 1
b
Write f in cycle form.
b. Let A = 51, 2, 3, 4, 56, and let g [ S A be given in cycle form by g = (2, 4, 5, 3). Write g in
array form.
■
If f and g are members of S A for some set A, then g + f [ S A , and the action of g + f on any member of A is determined by applying function f and then
function g. If f and g are cycles, g + f is still computed the same way.
example 39
If A = 51, 2, 3, 46 and f, g [ S A are given by f = (1, 2, 3) and g = (2, 3), then
g + f = (2, 3) + (1, 2, 3). But what does this composition function look like? Let’s
see what happens to element 1 of A. Working from right to left (first f, then g),
1 S 2 under f and then 2 S 3 under g, so 1 S 3 under g + f . If we want to write
g + f as a cycle, we see that it can start with
(1, 3
and we next need to see what happens to 3. Under f, 3 S 1 and then under g,
1 S 1 (because 1 does not appear in the cycle notation for g), so 3 S 1 under
g + f . Thus we can close the above cycle, writing it as (1, 3). But what happens to
2 and 4? If we consider 2, 2 S 3 under f and then 3 S 2 under g, so 2 S 2 under
g + f . Similarly, 4 S 4 under f and 4 S 4 under g, so 4 S 4 under g + f . We conclude that g + f = (1, 3).
In Example 39, if we were to compute f + g = (1, 2, 3) + (2, 3), we would get
(1, 2). (We already know that order is important in function composition.) If, however, f and g are members of S A and f and g are disjoint cycles—the cycles have
no elements in common—then f + g = g + f .