s
Section 5.4 Functions
409
53. Let A = 51, 2, 3, 4, 56. Write each of the following permutations on A in cycle form.
a. f = a
1 2 3 4 5
3 1 5 4 2
b
b. f = 5(1, 4), (2, 5), (3, 2), (4, 3), (5, 1)6
54. Let A 5a, b, c, d6. Write each of the following permutations on A in array form.
a. f = 5(a, c), (b, b), (c, d ), (d, a)6
b. f = (c, a, b, d )
c. f = (d, b, a)
d. f = (a, b) + (b, d ) + (c, a)
55. Let A be any set and let S A be the set of all permutations of A. Let f, g, h [ S A . Prove that the functions
h + (g + f ) and (h + g) + f are equal, thereby showing that we can write h + g + f without parentheses to
indicate grouping.
56. Find the composition of the following cycles representing permutations on A = 51, 2, 3, 4, 56. Write
your answer as a composition of one or more disjoint cycles.
a. (2, 4, 5, 3) + (1, 3)
b. (3, 5, 2) + (2, 1, 3) + (4, 1) (By Exercise 55, we can omit parentheses indicating grouping.)
c. (2, 4) + (1, 2, 5) + (2, 3, 1) + (5, 2)
57. Find the composition of the following cycles representing permutations on A = 51, 2, 3, 4, 5, 6, 7, 86.
Write your answer as a composition of one or more disjoint cycles.
a. (1, 3, 4) + (5, 1, 2)
b. (2, 7, 8) + (1, 2, 4, 6, 8)
c. (1, 3, 4) + (5, 6) + (2, 3, 5) + (6, 1)
d. (2, 7, 1, 3) + (2, 8, 7, 5) + (4, 2, 1, 8)
58. Find the composition of the following cycles representing permutations on N. Write your answer as a
composition of one or more disjoint cycles.
a. (3, 5, 2) + (6, 2, 4, 1) + (4, 8, 6, 2)
b. (1, 5, 13, 2, 6) + (3, 6, 4, 13) + (13, 2, 6, 1)
c (1, 2) + (1, 3) + (1, 4) + (1, 5)
59. Find the composition of the following cycles representing permutations on A = 5a, b, c, d, e6. Write your
answer as a composition of one or more disjoint cycles.
a. (a, d, c, e) + (d, c, b) + (e, c, a, d) + (a, c, b, d )
b. (e, b, a) + (b, e, d ) + (d, a)
c. (b, e, d ) + (d, a) + (e, a, c) + (a, c, b, e)
60. Find a permutation on an infinite set that cannot be written as a cycle.
61. The function f written in cycle form as f = (4, 2, 8, 3) is a bijection on the set N. Write f
−1
in cycle form.
62. The “pushdown store,” or “stack,” is a storage structure that operates much like a set of plates stacked on
a spring in a cafeteria. All storage locations are initially empty. An item of data is added to the top of the
stack by a “push” instruction, which pushes any previously stored items farther down in the stack. Only
the topmost item on the stack is accessible at any moment, and it is fetched and removed from the stack
by a “pop” instruction.
Let’s consider strings of integers that are an even number of characters in length; half the characters
are positive integers, and the other half are zeros. We process these strings through a pushdown store as
Section 5.4 Functions
409
53. Let A = 51, 2, 3, 4, 56. Write each of the following permutations on A in cycle form.
a. f = a
1 2 3 4 5
3 1 5 4 2
b
b. f = 5(1, 4), (2, 5), (3, 2), (4, 3), (5, 1)6
54. Let A 5a, b, c, d6. Write each of the following permutations on A in array form.
a. f = 5(a, c), (b, b), (c, d ), (d, a)6
b. f = (c, a, b, d )
c. f = (d, b, a)
d. f = (a, b) + (b, d ) + (c, a)
55. Let A be any set and let S A be the set of all permutations of A. Let f, g, h [ S A . Prove that the functions
h + (g + f ) and (h + g) + f are equal, thereby showing that we can write h + g + f without parentheses to
indicate grouping.
56. Find the composition of the following cycles representing permutations on A = 51, 2, 3, 4, 56. Write
your answer as a composition of one or more disjoint cycles.
a. (2, 4, 5, 3) + (1, 3)
b. (3, 5, 2) + (2, 1, 3) + (4, 1) (By Exercise 55, we can omit parentheses indicating grouping.)
c. (2, 4) + (1, 2, 5) + (2, 3, 1) + (5, 2)
57. Find the composition of the following cycles representing permutations on A = 51, 2, 3, 4, 5, 6, 7, 86.
Write your answer as a composition of one or more disjoint cycles.
a. (1, 3, 4) + (5, 1, 2)
b. (2, 7, 8) + (1, 2, 4, 6, 8)
c. (1, 3, 4) + (5, 6) + (2, 3, 5) + (6, 1)
d. (2, 7, 1, 3) + (2, 8, 7, 5) + (4, 2, 1, 8)
58. Find the composition of the following cycles representing permutations on N. Write your answer as a
composition of one or more disjoint cycles.
a. (3, 5, 2) + (6, 2, 4, 1) + (4, 8, 6, 2)
b. (1, 5, 13, 2, 6) + (3, 6, 4, 13) + (13, 2, 6, 1)
c (1, 2) + (1, 3) + (1, 4) + (1, 5)
59. Find the composition of the following cycles representing permutations on A = 5a, b, c, d, e6. Write your
answer as a composition of one or more disjoint cycles.
a. (a, d, c, e) + (d, c, b) + (e, c, a, d) + (a, c, b, d )
b. (e, b, a) + (b, e, d ) + (d, a)
c. (b, e, d ) + (d, a) + (e, a, c) + (a, c, b, e)
60. Find a permutation on an infinite set that cannot be written as a cycle.
61. The function f written in cycle form as f = (4, 2, 8, 3) is a bijection on the set N. Write f
−1
in cycle form.
62. The “pushdown store,” or “stack,” is a storage structure that operates much like a set of plates stacked on
a spring in a cafeteria. All storage locations are initially empty. An item of data is added to the top of the
stack by a “push” instruction, which pushes any previously stored items farther down in the stack. Only
the topmost item on the stack is accessible at any moment, and it is fetched and removed from the stack
by a “pop” instruction.
Let’s consider strings of integers that are an even number of characters in length; half the characters
are positive integers, and the other half are zeros. We process these strings through a pushdown store as