Counting the Relations (3)

4. Antisymmetric Relations:-

Here Diagonal elements have 2 choices but 

for non-diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.

let |A| =n then and R is a relation from A to A, so 

Total number of elements in R = n2 

Total number of Diagonal pair = n

Total number of Non- Diagonal pair = (n^{2}-n)/2 and each have 3 choices

So Total number of  Antisymmetric Relations = 3^{(n^{2}-n)/2}. 2^{n}

 

5. Asymmetric Relations:

Diagonal pairs have only one choice as they are not allowed here.

Non-Diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.
  • So total number of Asymmetric Relation3^{(n^{2}-n)/2}. 1^{n} =3^{(n^{2}-n)/2} 

 

 

 

 

 

 

0Comment