The Gateway to Computer Science Excellence

+4 votes

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 ______.

+12 votes

No.of relations on the 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 no-restriction on non-reflexive pairs.

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

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

probability that choosen relation is reflexive = $\frac{2^{(n^2-n)}}{2^{(n^2)}}$ = $\frac{2^{(6)}}{2^{(9)}}$ = 0.125

there are n reflexive pairs, and (n$^2$-n) non-reflexive pairs

for a relation which is reflexive, all reflexive pairs must present and no-restriction on non-reflexive pairs.

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

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

probability that choosen relation is reflexive = $\frac{2^{(n^2-n)}}{2^{(n^2)}}$ = $\frac{2^{(6)}}{2^{(9)}}$ = 0.125

+1 vote

$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.

- it can be in a relation
- 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 daigonal elements of the table so we need to select $(1,1),(2,2),(3,3) $ in every reflexive relation.

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

- it can be in a relation
- 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 daigonal elements)

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

0 votes

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)

0 votes

For a set with n elements,

The number of reflexive relations is 2^(n^2-n).

The total number of relations on a set with n elements is 2^ (n^2).

The probability of choosing the reflexive relation out of set of relations i s = 2^(n^2-n) /2^ (n^2) = 2^( n^2-n- n^2) = 2^(-n)

Given n=3, the probability will be 2^(-n) = ⅛ = 0.125

The number of reflexive relations is 2^(n^2-n).

The total number of relations on a set with n elements is 2^ (n^2).

The probability of choosing the reflexive relation out of set of relations i s = 2^(n^2-n) /2^ (n^2) = 2^( n^2-n- n^2) = 2^(-n)

Given n=3, the probability will be 2^(-n) = ⅛ = 0.125

52,217 questions

59,921 answers

201,115 comments

118,161 users