Exercise 9.1 Twelvefold Way
Consider the functions f : B → U, count the number of functions and fill in the blanks below. Express the results in binomial coefficients, factorials, or powers (AVOID double bracket notation for first two rows).
Domain
Codomain
Any
Injective
Surjective
distinguishable
distinguishable
indistinguishable
distinguishable
distinguishable
indistinguishable
indistinguishable
indistinguishable
where
(i) B = {1,2,3} and U = {1,2,3,4,5}.
(ii) B = {1,2,3,4,5} and U = {1,2,3}.
Exercise 9.2 Multichoosing Consider
x1 + x2 + x3 + x4 + x5 + x6 + x7 ≤ 100
What are the number of integer solutions if
(i) xi > 0 and = holds;
(ii) xi ≥ 0 and = holds;
(iii) xi > 0 and < holds; (iv) xi ≥ 0 and < holds; (v) xi ≥ 0.
AVOID double bracket notation in the final solution.
Exercise 9.3 Inclusion-Exclusion Principle
Find the number of solutions of the equation x1 + x2+ x3 + x4 = 17, where xi,i = 1,2,3,4, are nonnegative integers such that x1 ≤ 3,x2 ≤ 4,x3 ≤ 5, and x4 ≤ 8.
Exercise 9.4 Derangement
What is the probability that none of 10 people receives the correct hat if a hatcheck person hands their hats back randomly?
Exercise 9.5 Derangement
A machine that inserts letters into envelopes goes haywire and inserts letters randomly into envelopes. What is the probability that in a group of 100 letters
a) no letter is put into the correct envelope?
b) exactly one letter is put into the correct envelope?
c) exactly 98 letters are put into the correct envelopes?
d) exactly 99 letters are put into the correct envelopes?
e) all letters are put into the correct envelopes?
Exercise 9.6 Master Method
Find the O or Θ bound of T(n) for the following recurrence relation.
T T
