Number of Anti-Symmetric Relations

Question

Number of possible Anti-Symmetric relations possible on a set of Size 5 whose size is maximum?

 

My Work:

Whose Size is maximum means, we should take all reflexive pairs.

Okay, now we are left with $\frac{n(n-1)}{2}$ off-diagonal pairs.

We can have 3 choices for each such pair $(a,b),(b,a)$

Either take one of them or don’t take any of them.

So, the final answer must be $3^{\binom{5}{2}}$

But the answer was given to be 1024.

 

Please guide me to the correct thought process.

Comments

srestha nope  $2^n$ is  not required we have to take all reflexive ....it is 1

---

@techbd123

What should be the number of antisymmetric relations?

Is it $\mathbf {2^n3^{\frac{n^2-n}{2}}}$ or $\mathbf{2^n3^{\frac{n}{2}}}$?

---

NPTEL video on the same

Answer 1

Ans is 2^10 = 1024

For Maximum cardinality,

normally we have 2 choices for Reflexive pairs (a,a) but for maximum we must include all. so, no choice for (a,a) ordered pairs.

For non Reflexive ordered pairs normally we have 3 choices (either (a,b) or (b,a) or none) but for maximum cardinality of R we have two choices (either (a,b) or (b,a)). number of such pairs = (n^2 -n)/2

So, Number of possible Anti-Symmetric relations possible on a set of Size 5 whose size is maximum i.e. Antisymmetric Relation that has maximum cardinality. = 2^((n^2-n)/2)  = 2^10 as n=5 ,