Question

If $n\left(A\right)=n,n>0$ then which among the following statements are correct

• A. Number of relations on $A$ that are not reflexive $=\left(2^{n^2-n}\right)(2^n-1)$
• B. Number of relations on $A$ that are not reflexive $=\left(2^{n^2+n}\right)(2^n-1)$
• C. Number of relations on $A$ that are not symmetric
  $=2^{n^2}-2^{\frac{n(n+1)}{2}}$
• D. Number of relations on $A$ that are not symmetric
  $=2^{n^2}-2^{\frac{n(n-1)}{2}}$

Answer 1

Answer: (A), (C)

Number of relations on $A$ that are not symmetric

$=2^{n^2}-2^{\frac{n(n+1)}{2}}$
If $n\left(A\right)=n$
Let $A=\{a_1,a_2,a_3,\dots .,a_n\}$
$\Rightarrow A\times A=\left\{\begin{array}{c}(a_1,a_1),(a_1,a_2),\dots ,(a_1,a_n)\\ (a_2,a_1),(a_2,a_2),\dots ,(a_2,a_n)\\ .\\ .\\ .\\ .\\ (a_n,a_1),(a_n,a_2),\dots ,(a_n,a_n)\end{array}\right\}$
$n(A\times A)=n^2$
Let us Consider elements in $A\times A$ as
$\left(1\right)$Diagonal elements $D_1=\left\{\right(a_1,a_1),(a_2,a_2)...(a_n,a_n\left)\right\}$
$\left(2\right)$Non diagonal elements $D_2=\left\{\right(a_1,a_2),(a_2,a_1),(a_1,a_3),(a_3,a_1)...(a_{n-1},a_n),(a_n,a_{n-1}\left)\right\}$
$n\left(D_1\right)=n,n\left(D_2\right)=n^2-n$
Now for relation to be reflexive,
$\left(i\right)$ there is only one choice for diagonal elements i.e It has to be included to make relation reflexive
$\left(ii\right)$ for each of $n^2-n$ non diagonal elements, there are two choices either it can be included or excluded to make relation reflexive.
$\therefore$ from principle of counting, number of reflexive relations
$=1\times 1\times ...\times 1\left(n\text{times}\right)\times 2\times 2\times ...\times 2(n^2-n\text{times})$
$=2^{n^2-n}$
So, number of reflexive relations$=2^{n^2-n}$
$\therefore$ number of relations which are not reflexive $=2^{n^2}-2^{n^2-n}=2^{n^2}(1-\frac{1}{2^n})=2^{n^2-n}(2^n-1)$

Now for relation to be symmetric,
$\left(i\right)$ there are two choices for each of $n$ diagonal elements
$\left(ii\right)$ For $n^2-n$ non diagonal elements we can form pairs of $(a_1,a_2),(a_2,a_1);(a_1,a_3)(a_3,a_1);(a_{n-1},a_n)(a_n,a_{n-1});$
for each pair there are two choices, either it can be included or excluded to make relation symmetric.
From principle of counting number of symmetric relations
$=2\times 2\times ...2\left(n\text{times}\right)\times 2\times 2\times ...2\left(\frac{n^2-n}{2}\text{times}\right)=2^{\frac{n^2+n}{2}}$
So, number of symmetric relations $=2^{\frac{n^2+n}{2}}$
$\therefore$ number of relations which are not symmetric $=2^{n^2}-2^{\frac{n^2+n}{2}}$