GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
107 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 (14.6k points)   | 107 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.7k 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 Mar 2017
  1. rude

    4768 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2728 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1378 Points

  9. Bikram

    1350 Points

  10. Sanjay Sharma

    1126 Points

Monthly Topper: Rs. 500 gift card

21,519 questions
26,847 answers
61,164 comments
23,187 users