GATE CSE 2020 | Question: 17

Question

Let $\mathcal{R}$ be the set of all binary relations on the set $\{1,2,3\}$. Suppose a relation is chosen from $\mathcal{R}$ at random. The probability that the chosen relation is reflexive (round off to $3$ decimal places) is ______.

Comments

The probability that the chosen relation is symmetric is: https://gateoverflow.in/355766/cmi-2020-datascience-b-13

---

…………………………….

Note that diagonal elements can only be selected in one direction, while non-diagonal elements can only be selected in two directions (yes, that element is present; no, that element is not present), and there are n^2 - n such elements.

---

@Mohitdas You should post your answers in answer  section rather then commenting below the answer section

---

Focus on learning @abir_banerjee

NO one is asking for your suggestion don’t tag people for silly things 

Answer 1

No. of relations on set $A$ with $n$ elements $=2^{n*n}$

There are $n$ reflexive pairs, and $n^2-n$ non-reflexive pairs

For a relation which is reflexive, all reflexive pairs must present and are no-restrictions on the non-reflexive pairs.

So, there are two possibilities for non-reflexive pairs- present or absent.

∴ No.of reflexive relations $=1.2^{(n^2-n)}$

Probability that a chosen relation is reflexive $=\frac{2^{(n^2-n)}}{2^{n^2}} = \frac{2^{6}}{2^{9}} = 0.125$

Answer 2

	$1$	$2$	$3$
$1$	$(1,1)$	$(1,2)$	$(1,3)$
$2$	$(2,1)$	$(2,2)$	$(2,3)$
$3$	$(3,1)$	$(3,2)$	$(3,3)$

Now each of the cells have $2$ possibility i.e.

1. it can be in a relation
2. it cannot appear in the relation

Hence total number of relations possible$=2*2*2*2*2*2*2*2*2=2^9$

---

For any relation to be reflexive the relation should contain all the diagonal elements of the table so we need to select $(1,1),(2,2),(3,3) $ in every reflexive relation.

Now $6$ remaining cells(non-diagonal cells) can have $2$ possibilities

1. it can be in a relation
2. it cannot appear in the relation

Hence total number of reflexive relations possible$=1*1*1*2*2*2*2*2*2= 2^6$ ($1$ is possibility for selecting diagonal elements)

---

$\therefore$ Probability $=\frac{\text{Total number of reflexive relations}}{\text{Total number of relations}} = \frac{2^6}{2^9} =\frac{64}{512} = 0.125$

Comments

is (1,1) (2,2) (1,2) reflexive ????

---

Yes. if you consider the set as {1,2}.

Answer 3

S={1,2,3}

and  S×S =9 pair (just do cross product)

{ (11) (12) (13) (21) (22) (23) (31) (32) (33) }

out of 9 pair 3 pair should contain in set for reflexive that is (1,1) (2,2) (3,3) these 3 ordered pair should be in set and for remaining 6 pair(because total 9 pairs are in set) we have option either choose it or not...so favourable case = 2×2×2×2×2×2 =2^6

total case = 2^9 (because for relation we have 2 choices for each pair)

probability= 2^6 / 2^9 = 1/8 = 0.125

Answer = 0.125

Answer 4

The idea is same , just a different combinatoric approach (as it a counting problem only) :

# : no of (shorthand)

#reflexive relations = #supersets of identity relation on set A = {1,2,3}  (all reflexive relations are just supersets of identity relation only on any set)

 

identity relation, I = {(1,1),(2,2),(3,3)}   (they are fixed to appear in every reflexive relation , therefore these 3 pairs will create only 1 choice )

maximum #pairs in relation R = |AxA| = 3x3 = 9            (this is the biggest relation AxA only)

#binary relations on A     =    #subsets of AxA = $2^{9}$ = 512       (these are all possible binary relations on set A )

now the choices are created by non-reflexive pairs : (x,y) such that x, y are distinct  (every pair appear in reflexive relation or not – 2 choices)

#non-reflexive pairs = 3 x 2 = 6     (#permutations with non-repetitions)

#reflexive relations on A = 1x$2^{6}$  (1 is fixed for reflexive pairs and 2^6 for all subsets of non-reflexive pairs )

therefore, 

P(R is reflexive) = #reflexive rel / #binary relations on A = $\frac{2^{6}}{2^{9}}$ = 1/8 = 0.125