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 distinguishable indistinguishable distinguishable
Codomain distinguishable distinguishable indistinguishable
Any Injective Surjective
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.
1
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?
2
Exercise 9.6 Master Method
Find the O or Θ bound of T(n) for the following recurrence relation. (i) T(n) = 4T(n/4) + 5n.
(ii) T (n) = 4T (n/5) + 5n.
(iii) T (n) = 5T (n/4) + 4n.
(iv) T(n) = 4T(√n) + log5 n
(v) T(n) = 4T(√n) + log2 n
3
Reference
1. Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applica- tions: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
2. Fraleigh, John B. A first course in abstract algebra. Pearson Education India, 2003.
4
