GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
82 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 (11.7k points)   | 82 views

1 Answer

+4 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.5k 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 Jan 2017
  1. Debashish Deka

    9872 Points

  2. sudsho

    5596 Points

  3. Habibkhan

    5498 Points

  4. Bikram

    5350 Points

  5. Vijay Thakur

    4508 Points

  6. Arjun

    4458 Points

  7. Sushant Gokhale

    4410 Points

  8. saurabh rai

    4236 Points

  9. santhoshdevulapally

    3906 Points

  10. Kapil

    3892 Points

Monthly Topper: Rs. 500 gift card

19,481 questions
24,260 answers
54,210 comments
20,405 users