For a set A with n elements, how many relations on A are (i) symmetric and…
2012
For a set A with n elements, how many relations on A are (i) symmetric and (ii) both reflexive and symmetric?
Answer: D. 2n(n + 1)/2 and 2n(n − 1)/2 — ConceptA relation on A is a subset of A × A. Symmetry requires that, for distinct x and y, the ordered pairs (x, y) and (y, x) must be chosen together or…
- A.
2n(n + 1)/2 and 2n · 3n(n − 1)/2
- B.
3n(n − 1)/2 and 2n(n − 1)
- C.
2n(n + 1)/2 and 3n(n − 1)/2
- D.
2n(n + 1)/2 and 2n(n − 1)/2
Attempted by 26 students.
Show answer & explanation
Correct answer: D
Concept
A relation on A is a subset of A × A. Symmetry requires that, for distinct x and y, the ordered pairs (x, y) and (y, x) must be chosen together or omitted together.
Thus each diagonal pair (x, x) is an independent unit, while each unordered pair {x, y} with x ≠ y forms one off-diagonal unit. Reflexivity fixes every diagonal pair as present.
Application
There are n diagonal units and n(n − 1)/2 unordered off-diagonal units.
For a symmetric relation, every unit has two choices: include it or omit it. Hence the count is 2n + n(n − 1)/2 = 2n(n + 1)/2.
For a relation that is reflexive and symmetric, all n diagonal units are already fixed as included.
Only the n(n − 1)/2 off-diagonal units remain free, each with two choices. Hence the count is 2n(n − 1)/2.
Cross-check
For n = 1, there are two symmetric relations, namely the empty relation and {(a, a)}, but only one reflexive-symmetric relation, namely {(a, a)}. The formulas give 2 and 1 respectively.
Therefore, the required pair is 2n(n + 1)/2 and 2n(n − 1)/2.