Description

Exercise 7.1
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).
Elements of Domain Elements of Codomain Any f Injective f Surjective f
distinguishable distinguishable
indistinguishable distinguishable
where
1. B = {1,2,3} and U = {1,2,3,4,5}.
2. B = {1,2,3,4,5} and U = {1,2,3}.
Exercise 7.2
Derive the following formula for the Euler’s totient function φ

by applying the inclusion-exclusion principle to the set {1,2,…,n}.
Exercise 7.3 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 7.4
Find the Θ bound of T(n) for the following recurrence relation.

Exercise 7.5
(i) Let T(n;d1,…,dn) be the number of trees with n ≥ 2 vertices v1,…,vn, and degrees d(v1) = d1, d(v2) = d2, …, d(vn) = dn, with di ≥ 1. Show that

(ii) Show that d1,…,dn, with di ≥ 1, are degrees of a tree with n vertices iff
n
X
di = 2(n − 1)
i=1
(iii) Use (i) and (ii) prove that the number of spanning trees of Kn is nn−2.