GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
110 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)   | 110 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 Apr 2017
  1. akash.dinkar12

    3782 Points

  2. Divya Bharti

    2696 Points

  3. Deepthi_ts

    2270 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Sanjay Sharma

    1692 Points

  7. Debashish Deka

    1668 Points

  8. Shubham Sharma 2

    1610 Points

  9. Prashant.

    1580 Points

  10. Arjun

    1570 Points

Monthly Topper: Rs. 500 gift card

22,135 questions
28,125 answers
63,467 comments
24,261 users