Discrete Math for Computer Science  Assignment # 5

CS201: Discrete Math for Computer Science
 Assignment # 5

Q.1 Suppose that n ≥ 1 is an integer.
(a) How many functions are there from the set {1, 2, . . . , n} to the set
{1, 2, 3}?
(b) How many of the functions in part (a) are one-to-one functions?
(c) How many of the functions in part (a) are onto functions?
Q.2 How many functions are there from the set {1, 2, . . . , n}, where n is a
positive integer, to the set {0, 1}
(a) that are one-to-one?
(b) that assign 0 to both 1 and n?
(c) that assign 1 to exactly one of the positive integers less than n?
Q.3 Suppose that p and q are prime numbers and that n = pq. Use the
principle of inclusion-exclusion to find the number of positive integers not
exceeding n that are relatively prime to n, i.e., the Euler function φ(n).
Q.4 How many bit strings of length 6 have at least one of the following
properties:
• start with 010
• start with 11
• end with 00
State clearly how you count and get your answer.
Q.5
Consider all permutations of the letters A, B, C, D, E, F, G.
1
(a) How many of these permutations contains the strings ABC and DE
(each as consecutive substring)?
(b) In how many permutations does A precede B? (not necessary immediately)
Q.6 Alice is going to choose a selection of 12 chocolates. There are 25 different
brands of them and she can have as many as she wants of each brand (but
can only choose 12 pieces). How many ways can she make this selection?
Q.7 16 points are chosen inside a 5 × 3 rectangle. Prove that two of these
points lie within √
2 of each other.
Q.8 Let (xi
, yi), i = 1, 2, 3, 4, 5, be a set of five distinct points with integer
coordinates in the xy plane. Show that the midpoint of the line joining at
least one pair of these points has integers coordinates.
Q.9 Prove that at a party where there are at least two people, there are two
people who know the same number of other people there.
Q.10 Show that if p is a prime and k is an integer such that 1 ≤ k ≤ p − 1,
then p divides
p
k
?
.
Q.11 Prove the hockeystick identity
Xr
k=0
?
n + k
k
?
=
?
n + r + 1
r
?
whenever n and r are positive integers,
(a) using a combinatorial argument
(b) using Pascal’s identity.
Q.12
Solve the recurrence relation
an = 2an−1 + an−2 − 2an−3

with initial conditions a0 = 1, a1 = 0, and a2 = 7.
Q.13 Solve the recurrence relation
an = 4an−2,
with initial conditions a0 = 3, a1 = 2.
Q.14
(a) Find all solutions of the recurrence relation an = 2an−1 + 2n
2
.
(b) Find the solution of the recurrence relation in part (a) with initial
condition a1 = 4.
Q.15
Use generating functions to prove Pascal’s identity: C(n, r) = C(n −
1, r) + C(n − 1, r − 1) when n and r are positive integers with r < n. [Hint:
Use the identity (1 + x)
n = (1 + x)
n−1 + x(1 + x)
n−1
.]
Q.16 How many relations are there on a set with n elements that are
(a) symmetric?
(b) antisymmetric?
(c) irreflexive?
(d) reflexive and symmetric?
(e) neither reflexive nor irreflexive?
Q.17 Suppose that the relation R is symmetric. Show that R∗
is symmetric.
Q.18 Suppose that the relation R is irreflexive. Is the relation R2 necessarily
irreflexive?
Q.19 Let R be the relation on the set of ordered pairs of positive integers such
that ((a, b),(c, d)) ∈ R if and only if ad = bc. Show that R is an equivalence
relation.
3