GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
137 views

Let A = {1,2,3,4}. since each element of P(AxA) is subset of AxA, it is binary relation on A
Assuming each relation in P(AxA) is equally likely to be chosen,

i. what is the probability that a randomly chosen relation is reflexive
a.  1/26
b. 1/24
c. 1/26
d. 1/212
Given Ans: 1/24
ii what is the probability that a randomly chosen relation is Symmetric
a.  1/216
b. 1/24
c. 1/26
d. 1/212
Given Ans: 1/26

asked in Set Theory & Algebra by Veteran (15.1k points)   | 137 views

1 Answer

+5 votes
Best answer

 Total no. of relations on a set A of cardinality n  is $2^{n^{2}}$

i) No. of reflexive relations = $2^{n^{2} - n}$

Probability of reflexive relations = $\large \frac{2^{n^{2} - n}}{2^{n^{2}}}$  = $\large \frac{2^{4^{2} - 4}}{2^{4^{2}}}$

                                             = $\large \frac{1}{16}$

                                            = $\LARGE \frac{1}{2^{4}}$

ii) No. of symmetric relations =$\large 2^{\frac{n^{2}+n}{2}}$

Probability of symmetric relations = $\LARGE \frac{2^{\frac{n^{2}+n}{2}}}{2^{n^{2}}}$ = $\LARGE \frac{2^{\frac{4^{2}+4}{2}}}{2^{4^{2}}}$

                                                 =$\LARGE \frac{1}{64}$

                                                = $\LARGE \frac{1}{2^{6}}$

answered by Active (1.8k points)  
selected by
Perfect!!
great answer Rahul :) can u please tell us the formula for remaining properties also ( transitive, antisymm) also thanks :)

Anti Symmetric = $\LARGE 2^{n}*3^{\frac{n^{2}-n}{2}}$

Asymmetric = $\LARGE 3^{\frac{n^{2}-n}{2}}$

No formula exists for Transitive Relations!



Top Users Aug 2017
  1. Bikram

    4990 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3286 Points

  5. rahul sharma 5

    3166 Points

  6. makhdoom ghaya

    2510 Points

  7. just_bhavana

    2398 Points

  8. stblue

    2144 Points

  9. Tesla!

    2066 Points

  10. joshi_nitish

    1796 Points


25,022 questions
32,160 answers
74,903 comments
30,202 users