Question

On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?

Please explain how to calculate .

Answer 1

On a set $S$ with $n$ elements how many relations are there?

A relation consists of set of ordered pairs $(a,b)$. Here $a$ can be chosen in $n$ ways and similarly $b$ can be chosen in $n$ ways. So, totally $n^2$ possible ordered pairs are possible for a relation. Now each of these ordered pair can either be present in the relation or not- 2 possibilities for each of the $n^2$ pair. So, total number of possible relations =  $$2^{\left(n^2\right)}.$$

Now, for a relation $R$ to be reflexive, ordered pairs $\left\{(a,a) \mid a \in S \right\}$, must be present in $R$. i.e.; the relation set $R$ must have $n$ ordered pairs fixed. So, number of ordered pairs possible is $ n^2 - n$ and hence total number of reflexive relations is equal to

$$ 2^{\left(n^2-n\right)}.$$

Number of irreflexive relations is same as number of reflexive relations. In reflexive relations we always included $n$ ordered pairs for  $\left\{(a,a) \mid a \in S \right\}$, while in irreflexive relation we always omit those $n$ ordered pairs. So, the number of ordered pairs to choose for the relation is the same for both reflexive as well as irreflexive relations which is  $$2^{\left( n^2-n\right)}.$$

A relation becomes symmetric, if for ordered pair $(a,b)$ in $R$, ordered pair $(b,a)$ is also present in $R$. So, here, the total number of ordered pairs possible is reduced from

$n + n + \dots + n$ to

$n + n-1 + n-2 + \dots +1 = \frac{n (n+1)}{2}$.

So, total number of possible symmetric relations = $$2^{\left( \frac{n (n+1)}{2}\right)}.$$

A relation becomes anti-symmetric if for the ordered pairs $(a,b)$ and $(b,a)$ in $R$, $a=b$. i.e., the pairs $(a,b) $ and $(b,a)$ cannot be simultaneously be in the relation unless $a = b$. 

For the $n$ pairs $(a,a)$ in $R$, they can be either present in relation or absent. So, 2 possibilities for each giving $2^n$ possible relations. 

Number of pairs $(a,b)$ in $R$ such that $a \neq b $ equals number of ways of selecting 2 numbers from $n$ without repetition, equals $ \frac {n (n-1)}{2}$ 

Now, for each of these pairs $(a,b)$, there are 3 possibilities-

1. $(a,b)$ and $(b,a)$ not in $R$
2. $(a,b)$ in $R$ but $(b,a)$ not in $R$
3. $(a,b)$ not in $R$ but $(b,a)$ in $R$

So, total number of possibilities for all such pairs = $3^{\left( \frac{n(n-1)}{2}\right)}$.

And total number of anti-symmetric relations on a set of $n$ elements becomes $$2^n \times 3^{\left( \frac{n(n-1)}{2}\right)}.$$

---

Finally, coming to your question, number of relations that are both irreflexive and anti-symmetric which will be same as the number of relations that are both reflexive and antisymmetric is

$$3^{\left(\frac{n(n-1)}{2}\right)}.$$

We just have to always exclude $n$ pairs being considered for $(a,a)$ while calculating the possible relations for anti-symmetric case. 

Comments

1. For symmetric relation for element 1 -say a- it has n choices to relate to, for element 2 -say b - it has only n-1 choices (b,a) is already present due to (a,b) being there and relation being symmetric. Now for 3rd element n-2 and so on.

2. No. of irreflexive relations = X, no. of anti-symmetric relations = Y, then no. of irreflexive and anti-symmetric relations = ?

All we can say is it is  <= min(X,Y). i.e., to calculate the pair of conditional relations we have to start from beginning of derivation and apply both conditions.

---

I have understand the 1st one.

In case of 2nd one, Consider X = $2^{\frac{n(n+1)}{2}}$ i.e. no of irreflexive relations and Y = $2^{n} \times 3^{\frac{n(n-1)}{2}}$ i.e. no of anti-symmetric relations. Now if we want min(X, Y), if I am not wrong then the answer should be X, which is not same with above answer.

number of relations that are both irreflexive and anti-symmetric is $3^{\frac{n(n-1)}{2}}$. How do we get this? This is not just minimum.

Please tell me where I am doing wrong?

---

I did not tell it is minimum. I told it won't be greater than the minimum. To get the actual value we have to start the derivation from beginning- you can read the last part of answer once more.

Answer 2

Answer should be $2^{n}-1 * 3 ^{\frac{n^{2} - n}{2} }$

Consider this example {1,2,3}

relations pairs:-

(11 , 22 ,33 ) Call it part 1,

(12 , 21

13, 31

23, 32 ) call it part 2

Now for part 1 to be irreflexive and antisymmetric we will have 7 possibilities as we cannot include (11 , 22, 33) since it will make it reflexive. In rest every other case, the relations will be irreflexive as well as antisymmetric. So for n elements, we'll have $2^{n}-1$ such possibilities.

Now for part 2 to be irreflexive and antisymmetric, we will have $3 ^{\frac{n^{2} - n}{2} }$ possibilities. Note that Part 2 cant spoil the irreflexivity as irreflexive property only depends on the relation pair having same elements, that we included in part 1.

 

So total will be part1 * part2 ie.,  $2^{n}-1 * 3 ^{\frac{n^{2} - n}{2} }$

The answer is not taken from any reference book and hence may be wrong

Comments

irreflexive means including all non-diagonal relations in the set.

antisymmetric means including all diagonals(optional) and nonpair elements in the set.

now when both come to the picture we only count intersection of these two.

i.e,1. we first delete all n diagonal elements(suppose |A*A|=n^2)

     2.we pair up all n^2-n elements taking adjacent two at a time which exactly counts [n^2-n]/2.

     3. last but not the least,  each relation among [n^2-n]/2, they have 3 choices, to come first relation or second relation or none of them.

so total number =3,3,3,...............,[n^2-n]/2 times

                          = 3^[[n^2-n]/2]        SIMPLE,ISN'T IT!!!  :)