410
Relations, Functions, and Matrices
follows: As we read from left to right, the push instruction is applied to any nonzero integer, and a zero
causes the pop instruction to be applied to the stack, thus printing the popped integer. Thus, processing
the string 12030040 results in an output of 2314, and processing 12304000 results in an output of 3421.
(A string such as 10020340 cannot be handled by this procedure because we cannot pop two integers from
a stack containing only one integer.) Both 2314 and 3421 can be thought of as permutations,
a
1 2 3 4
2 3 1 4
b
and
a
1 2 3 4
3 4 2 1
b
respectively, on the set A = 51, 2, 3, 46.
a. What permutation of A = 51, 2, 3, 46 is generated by applying this procedure to the string 12003400?
b. Name a permutation of A = 51, 2, 3, 46 that cannot be generated from any string where the digits 1, 2,
3, and 4 appear in order, no matter where the zeros are placed.
63. Let S = 52, 4, 6, 86 and T = 51, 5, 76.
a. Find the number of functions from S to T.
b. Find the number of onto functions from S to T.
64. Let S = 5P, Q, R6 and T = 5k, l, m, n6.
a. Find the number of functions from S to T.
b. Find the number of one-to-one functions from S to T.
65. a. For 0 S 0 = 2, 3, and 4, respectively, use the theorem on the number of functions to show that the number
of one-to-one functions from S to S equals the number of onto functions from S to S.
b. Argue that for 0 S 0 = n, f : S S S is one-to-one if and only if f is onto.
c. Find an infinite set S and a function f : S S S such that f is one-to-one but not onto.
d. Find an infinite set S and a function f : S S S such that f is onto but not one-to-one.
66. Let A = 5a, b, c, d6. How many functions are in S A ? How many of these functions are derangements?
Write all the derangements in array form.
67. Let 0 S 0 = n. In parts a-e, find the number of
a. functions from S to S.
b. one-to-one functions from S to S.
c. functions from S onto S (see Exercise 65).
d. permutations from S onto S.
e. derangements from S onto S.
f. Order the values obtained in parts (a) through (e) from smallest to largest and explain why this ordering
is reasonable.
68. a. A system development project calls for five different tasks to be assigned to Maria, Jon, and Suzanne.
In how many ways can the assignment be done if each of the three workers must get at least one task?
b. In how many ways can the projects be assigned if Maria must develop the test plan, which is one of the
five tasks, but may do other tasks as well? (Hint: Consider the two cases where Maria does and does
not do any of the other tasks.)
69. In a programming class of seven students, the instructor wants each student to modify the program from a
previous assignment, but no student should work on his or her own program. In how many ways can the
instructor assign programs to the students?
Relations, Functions, and Matrices
follows: As we read from left to right, the push instruction is applied to any nonzero integer, and a zero
causes the pop instruction to be applied to the stack, thus printing the popped integer. Thus, processing
the string 12030040 results in an output of 2314, and processing 12304000 results in an output of 3421.
(A string such as 10020340 cannot be handled by this procedure because we cannot pop two integers from
a stack containing only one integer.) Both 2314 and 3421 can be thought of as permutations,
a
1 2 3 4
2 3 1 4
b
and
a
1 2 3 4
3 4 2 1
b
respectively, on the set A = 51, 2, 3, 46.
a. What permutation of A = 51, 2, 3, 46 is generated by applying this procedure to the string 12003400?
b. Name a permutation of A = 51, 2, 3, 46 that cannot be generated from any string where the digits 1, 2,
3, and 4 appear in order, no matter where the zeros are placed.
63. Let S = 52, 4, 6, 86 and T = 51, 5, 76.
a. Find the number of functions from S to T.
b. Find the number of onto functions from S to T.
64. Let S = 5P, Q, R6 and T = 5k, l, m, n6.
a. Find the number of functions from S to T.
b. Find the number of one-to-one functions from S to T.
65. a. For 0 S 0 = 2, 3, and 4, respectively, use the theorem on the number of functions to show that the number
of one-to-one functions from S to S equals the number of onto functions from S to S.
b. Argue that for 0 S 0 = n, f : S S S is one-to-one if and only if f is onto.
c. Find an infinite set S and a function f : S S S such that f is one-to-one but not onto.
d. Find an infinite set S and a function f : S S S such that f is onto but not one-to-one.
66. Let A = 5a, b, c, d6. How many functions are in S A ? How many of these functions are derangements?
Write all the derangements in array form.
67. Let 0 S 0 = n. In parts a-e, find the number of
a. functions from S to S.
b. one-to-one functions from S to S.
c. functions from S onto S (see Exercise 65).
d. permutations from S onto S.
e. derangements from S onto S.
f. Order the values obtained in parts (a) through (e) from smallest to largest and explain why this ordering
is reasonable.
68. a. A system development project calls for five different tasks to be assigned to Maria, Jon, and Suzanne.
In how many ways can the assignment be done if each of the three workers must get at least one task?
b. In how many ways can the projects be assigned if Maria must develop the test plan, which is one of the
five tasks, but may do other tasks as well? (Hint: Consider the two cases where Maria does and does
not do any of the other tasks.)
69. In a programming class of seven students, the instructor wants each student to modify the program from a
previous assignment, but no student should work on his or her own program. In how many ways can the
instructor assign programs to the students?