GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
166 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 (16.4k points) 15 135 253 | 166 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 (2.4k points) 3 8 23
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!



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8960 Points

  4. srestha

    6450 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4032 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Notable Question Sedhu Raman
Notable Question cse23
Notable Question vishwa ratna
Notable Question learner_geek
Popular Question Devshree Dubey
Popular Question nish kim
Popular Question Simar sandhu
Popular Question Rashi Gupta
Notable Question Akriti sood
Popular Question Samujjal Das
27,407 questions
35,256 answers
84,506 comments
33,480 users