PrepRung

JEE Main 2017 · Mathematics · Sets, Relations and Functions · hard

The number of relations on the set \1,2,3,4\ that are reflexive and symmetric but not transitive is

Single correct option

The number of relations on the set {1,2,3,4}\{1,2,3,4\} that are reflexive and symmetric but not transitive is
  1. A. 1515
  2. B. 4949
  3. C. 6464
  4. D. 6363
Show answer and solution

Answer: (B) 4949

A reflexive relation must contain the 44 pairs (i,i)(i,i). Symmetry means each of the (42)=6\binom42=6 unordered pairs {i,j}\{i,j\} is either included (both (i,j),(j,i)(i,j),(j,i)) or not, so there are 26=642^6=64 reflexive symmetric relations. Of these, the transitive ones are exactly the equivalence relations, which correspond to partitions of a 44-element set: 1+7+6+1=151+7+6+1=15 (the Bell number B4B_4). Hence the required number is 64−15=4964-15=49. A brute-force count over all 2162^{16} relations confirms this.
Report a mistake

Original question written in the JEE Main 2017 pattern and checked twice for the correct answer. Not an official question paper. How we write and check questions · Corrections policy · Report a mistake