Discrete Mathematics Multiple Choice Questions on “Number of Relations”.
1. How many binary relations are there on a set S with 9 distinct elements?
a) 290
b) 2100
c) 281
d) 260
Answer: c
Clarification: S is the set with 9 elements. A relation on S is defined as S x S. There are 92 number of ordered pairs in relation. So, the number of binary relations is 2(9*9) = 281.
2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2110
b) 3121
c) 290
d) 2132
Answer: a
Clarification: Let A be a set consists of n distinct elements. There are 2(n*n)-n number of reflexive relations that can be formed. So, here the answer is 2(11*11)-11 = 2110.
3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4120
b) 270
c) 3201
d) 291
Answer: d
Clarification: Let A be a set consists of n distinct elements. There are 2(n*(n-1))/2 number of reflexive and symmetric relations that can be formed. So, here the answer is 214*(14-1)/2 = 291.
4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2196
b) 250
c) 2320
d) 278
Answer: a
Clarification: Let S be a set consists of n distinct elements. There are 2(n-1)*(n-1) number of reflexive and symmetric relations that can be formed. So, here the answer is 2(15-1)*(15-1) = 2196.
5. Suppose S is a finite set with 7 elements. How many elements are there in the largest equivalence relation on S?
a) 56
b) 78
c) 49
d) 100
Answer: c
Clarification: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and transitive property. The largest equivalence relation means it should contain the largest number of ordered pairs. Since we can have n2 ordered pairs in R x R where n belongs to S and all these ordered pairs are present in this relation; its the largest equivalence relation.So there are n2 elements i.e 72 = 49 elements in the largest equivalence relation.
6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 320
b) 2400
c) 20
d) 1
Answer: d
Clarification: The rank of an equivalence relation is the number of an equivalence classes. If we have a1, a2, a3, …, an elements then a1 and a2 will be in the same equivalence class because everything is related and so on. In this case, there is only one equivalence class.
7. How many elements are there in the smallest equivalence relation on a set with 8 elements?
a) 102
b) 8
c) 48
d) 32
Answer: b
Clarification: Let R is an equivalence relation on the set S with n elements and so it satisfies reflexive, symmetric and transitive properties. The smallest equivalence relation means it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it must always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.
8. The rank of smallest equivalence relation on a set with 12 distinct elements is _______
a) 12
b) 144
c) 136
d) 79
Answer: a
Clarification: In the case of smallest equivalence relation, each element is in one equivalence class like {a1}, {a2}, … are equivalence classes. So, the rank or number of equivalence classes is n for a set with n elements and so the answer is 12.
9. If a set A has 8 elements and a set B has 10 elements, how many relations are there from A to B?
a) 290
b) 380
c) 164
d) 280
Answer: d
Clarification: Let, a relation R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the powerset) is 2mn, there are 2mn number of relations from A to B and so the answer is 280.
10. Synonym for binary relation is _______
a) equivalence relation
b) dyadic relation
c) orthogonal relation
d) one to many relations
Answer: b
Clarification: A binary relation on a set S is a set of ordered pairs of elements of S. It is a subset of the cartesian product S2 = S x S. The terms correspondence, dyadic relation and 2-place relation are synonyms for the binary relation.