retagged by
9,051 views
15 votes
15 votes
Let $\mathcal{R}$ be the set of all binary relations on the set $\{1,2,3\}$. Suppose a relation is chosen from $\mathcal{R}$ at random. The probability that the chosen relation is reflexive (round off to $3$ decimal places) is ______.
retagged by

5 Answers

Best answer
32 votes
32 votes
No. of relations on set $A$ with $n$ elements $=2^{n*n}$

There are $n$ reflexive pairs, and $n^2-n$ non-reflexive pairs

For a relation which is reflexive, all reflexive pairs must present and are no-restrictions on the non-reflexive pairs.

So, there are two possibilities for non-reflexive pairs- present or absent.

∴ No.of reflexive relations $=1.2^{(n^2-n)}$

Probability that a chosen relation is reflexive $=\frac{2^{(n^2-n)}}{2^{n^2}} = \frac{2^{6}}{2^{9}} = 0.125$
edited by
31 votes
31 votes
  $1$ $2$ $3$
$1$ $(1,1)$ $(1,2)$ $(1,3)$
$2$ $(2,1)$ $(2,2)$ $(2,3)$
$3$ $(3,1)$ $(3,2)$ $(3,3)$

Now each of the cells have $2$ possibility i.e.

  1. it can be in a relation
  2. it cannot appear in the relation

Hence total number of relations possible$=2*2*2*2*2*2*2*2*2=2^9$


For any relation to be reflexive the relation should contain all the diagonal elements of the table so we need to select $(1,1),(2,2),(3,3) $ in every reflexive relation.

Now $6$ remaining cells(non-diagonal cells) can have $2$ possibilities

  1. it can be in a relation
  2. it cannot appear in the relation

Hence total number of reflexive relations possible$=1*1*1*2*2*2*2*2*2= 2^6$ ($1$ is possibility for selecting diagonal elements)


$\therefore$ Probability $=\frac{\text{Total number of reflexive relations}}{\text{Total number of relations}} = \frac{2^6}{2^9} =\frac{64}{512} = 0.125$

edited by
4 votes
4 votes

S={1,2,3}

and  S×S =9 pair (just do cross product)

{ (11) (12) (13) (21) (22) (23) (31) (32) (33) }

out of 9 pair 3 pair should contain in set for reflexive that is (1,1) (2,2) (3,3) these 3 ordered pair should be in set and for remaining 6 pair(because total 9 pairs are in set) we have option either choose it or not...so favourable case = 2×2×2×2×2×2 =2^6

total case = 2^9 (because for relation we have 2 choices for each pair)

probability= 2^6 / 2^9 = 1/8 = 0.125

Answer = 0.125

0 votes
0 votes

The idea is same , just a different combinatoric approach (as it a counting problem only) :

# : no of (shorthand)

#reflexive relations = #supersets of identity relation on set A = {1,2,3}  (all reflexive relations are just supersets of identity relation only on any set)

 

identity relation, I = {(1,1),(2,2),(3,3)}   (they are fixed to appear in every reflexive relation , therefore these 3 pairs will create only 1 choice )

maximum #pairs in relation R = |AxA| = 3x3 = 9            (this is the biggest relation AxA only)

#binary relations on A     =    #subsets of AxA = $2^{9}$ = 512       (these are all possible binary relations on set A )

now the choices are created by non-reflexive pairs : (x,y) such that x, y are distinct  (every pair appear in reflexive relation or not – 2 choices)

#non-reflexive pairs = 3 x 2 = 6     (#permutations with non-repetitions)

#reflexive relations on A = 1x$2^{6}$  (1 is fixed for reflexive pairs and 2^6 for all subsets of non-reflexive pairs )

therefore, 

P(R is reflexive) = #reflexive rel / #binary relations on A = $\frac{2^{6}}{2^{9}}$ = 1/8 = 0.125

 

Answer:

Related questions

24 votes
24 votes
2 answers
1
Arjun asked Feb 12, 2020
12,129 views
For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigm...
15 votes
15 votes
4 answers
2
Arjun asked Feb 12, 2020
9,066 views
Let $G$ be a group of $35$ elements. Then the largest possible size of a subgroup of $G$ other than $G$ itself is _______.
12 votes
12 votes
2 answers
3
17 votes
17 votes
4 answers
4
Arjun asked Feb 12, 2020
9,584 views
If there are $m$ input lines and $n$ output lines for a decoder that is used to uniquely address a byte addressable $1$ KB RAM, then the minimum value of $m+n$ is _______...