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
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
Elements of Codomain
Any f
Injective f
Surjective f
distinguishable
Derive the following formula for the Euler’s totient function φ
1
φ(n) = n
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>0and=holds;
- (ii) xi≥0and=holds;
- (iii) xi>0and<holds;
- (iv) xi≥0and<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. (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
Exercise 7.5
p|n
The purpose of this problem is to prove that the number of spanning trees of the complete graph Kn, n ≥ 2, is nn−2, a formula due to Cayley (1889).1
(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
n−2 T(n;d1,…,dn)= d1 −1,d2 −1,…,dn −1
(ii) Show that d1,…,dn, with di ≥ 1, are degrees of a tree with n vertices iff n
di =2(n−1) i=1
(iii) Use (i) and (ii) prove that the number of spanning trees of Kn is nn−2. 1For hints, see Gallier, p. 254
1 − p
Page 1 of 1