s
Section 5.4 Functions
411
70. a. Find a calculus book and look up the Maclaurin series representation for the function e
x
.
b. Use the answer to part (a) to find a series representation for e
−1
.
c. Use a calculator to compute an approximate value for e
−1
to about 5 decimal places.
d. How can the answer to parts (b) and (c) help you approximate the number of derangements of n objects
when n is large, say, n ≥ 10? (Hint: Look at Equation (4) in this section.)
e. Apply this approach to Exercise 69 and compare the results.
f. Approximately how many derangements are there of 10 objects?
71. Let f be a function, f : S S T .
a. Define a binary relation r on S by x r y 4 f (x) = f (y). Prove that r is an equivalence relation.
b. What can be said about the equivalence classes if f is a one-to-one function?
c. For S = T = Z and f (x) = 3x
2
, what is 34 4 under the equivalence relation of part (a)?
72. Prove that S(m, n), the number of ways to partition a set of m elements into n blocks, is equal to 1∙n!
times the number of onto functions from a set with m elements to a set with n elements. (Hint: Consider
Exercise 71.)
73. By the definition of a function f from S to T, f is a subset of S × T where the image of every s [ S under
f is uniquely determined as the second component of the ordered pair (s, t) in f. Now consider any binary
relation r from S to T. The relation r is a subset of S × T in which some elements of S may not appear
at all as first components of an ordered pair and some may appear more than once. We can view r as a
nondeterministic function from a subset of S to T. An s [ S not appearing as the first component of an
ordered pair represents an element outside the domain of r. For an s [ S appearing once or more as a first
component, r can select for the image of s any one of the corresponding second components.
Let S = 51, 2, 36, T = 5a, b, c6, and U = 5m, n, o, p6. Let r be a binary relation on S × T and s be
a binary relation on T × U defined by
r = 5(1, a), (1, b), (2, b), (2, c), (3, c)6
s = 5(a, m), (a, o), (a, p), (b, n), (b, p), (c, o)6
Thinking of r and s as nondeterministic functions from S to T and T to U, respectively, we can form
the composition s + r, a nondeterministic function from S to U.
a. What is the set of possible images of 1 under s + r?
b. What is the set of possible images of 2 under s + r? of 3?
74. Let f be a function, f: S S T .
a. Show that for all subsets A and B of S, f (A d B) # f (A) d f(B).
b. Show that f (A d B) = f (A) d f(B) for all subsets A and B of S if and only if f is one-to-one.
75. Let C be a collection of sets, and define a binary relation r on C as follows: For S, T [ C, S r T 4 S is
equivalent to T. Show that r is an equivalence relation on C.
76. Group the following sets into equivalence classes according to the equivalence relation of Exercise 75.
A = 52, 46
B = N
C = 5x 0 x [ N and ( E y)( y [ N and x = 2*y)6
D = 5a, b, c, d6
E = `(51, 26)
F = Q
+
Section 5.4 Functions
411
70. a. Find a calculus book and look up the Maclaurin series representation for the function e
x
.
b. Use the answer to part (a) to find a series representation for e
−1
.
c. Use a calculator to compute an approximate value for e
−1
to about 5 decimal places.
d. How can the answer to parts (b) and (c) help you approximate the number of derangements of n objects
when n is large, say, n ≥ 10? (Hint: Look at Equation (4) in this section.)
e. Apply this approach to Exercise 69 and compare the results.
f. Approximately how many derangements are there of 10 objects?
71. Let f be a function, f : S S T .
a. Define a binary relation r on S by x r y 4 f (x) = f (y). Prove that r is an equivalence relation.
b. What can be said about the equivalence classes if f is a one-to-one function?
c. For S = T = Z and f (x) = 3x
2
, what is 34 4 under the equivalence relation of part (a)?
72. Prove that S(m, n), the number of ways to partition a set of m elements into n blocks, is equal to 1∙n!
times the number of onto functions from a set with m elements to a set with n elements. (Hint: Consider
Exercise 71.)
73. By the definition of a function f from S to T, f is a subset of S × T where the image of every s [ S under
f is uniquely determined as the second component of the ordered pair (s, t) in f. Now consider any binary
relation r from S to T. The relation r is a subset of S × T in which some elements of S may not appear
at all as first components of an ordered pair and some may appear more than once. We can view r as a
nondeterministic function from a subset of S to T. An s [ S not appearing as the first component of an
ordered pair represents an element outside the domain of r. For an s [ S appearing once or more as a first
component, r can select for the image of s any one of the corresponding second components.
Let S = 51, 2, 36, T = 5a, b, c6, and U = 5m, n, o, p6. Let r be a binary relation on S × T and s be
a binary relation on T × U defined by
r = 5(1, a), (1, b), (2, b), (2, c), (3, c)6
s = 5(a, m), (a, o), (a, p), (b, n), (b, p), (c, o)6
Thinking of r and s as nondeterministic functions from S to T and T to U, respectively, we can form
the composition s + r, a nondeterministic function from S to U.
a. What is the set of possible images of 1 under s + r?
b. What is the set of possible images of 2 under s + r? of 3?
74. Let f be a function, f: S S T .
a. Show that for all subsets A and B of S, f (A d B) # f (A) d f(B).
b. Show that f (A d B) = f (A) d f(B) for all subsets A and B of S if and only if f is one-to-one.
75. Let C be a collection of sets, and define a binary relation r on C as follows: For S, T [ C, S r T 4 S is
equivalent to T. Show that r is an equivalence relation on C.
76. Group the following sets into equivalence classes according to the equivalence relation of Exercise 75.
A = 52, 46
B = N
C = 5x 0 x [ N and ( E y)( y [ N and x = 2*y)6
D = 5a, b, c, d6
E = `(51, 26)
F = Q
+