Couting the Relations

let A  and B are set such that |A| =n  and |B| = m

then  |A*B| = m*n

Relation: It is a subset of cartesian product.

Since already we know |A*B| = m*n and each element in the cartesian product have two choices: either they want to be the part of the relation of they don't want. 

2 choices for m*n elements so total no. relations possible = 2m*n


we have already discussed the types of relations. So let's know some more details:

1. Number of Reflexive relations:-

let |A| = n

Reflexive relations are always defined on the same set :

|A*A| = n2 

if there are n elements in the set then there will be n reflexive pairs like (1,1), (2,2) ... (n,n)

So all these pairs must be present in  reflexive pairs so out of n2 elements n has one choice as they must be the part of relation but remaining  n2 -n has two choice 

So total number of reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}


2. The number of Ir-Reflexive relations:

Again those reflexive pairs have only one choice they must not be present so: one choice for 'n' elements and two choices for n2 -n elements.

total number of Ir- reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}