retagged by
25,919 views

2 Answers

Best answer
38 votes
38 votes

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. 

edited by
0 votes
0 votes
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
edited by

Related questions

2 votes
2 votes
1 answer
1
4 votes
4 votes
4 answers
2
admin asked Oct 9, 2015
5,320 views
I just want to know how the value in the answers come like 2^n2 and 2^n^2-1 etc. Please make it clear.
2 votes
2 votes
0 answers
3