How to find the number of anti-symmetric relations?
3^(n(n-1)/2)
google is your friend, as is your textbook ...
would be awesome if there is explanation.thanks
To find the number of anti-symmetric relations, we need to understand what an anti-symmetric relation is first.
A relation R on a set A is called anti-symmetric if for every (a, b) ∈ R, then (b, a) is not in R whenever a ≠ b. In other words, if (a, b) is in R and a ≠ b, then (b, a) cannot be in R.
To find the number of anti-symmetric relations on a set with n elements, we can use the following approach:
1. Consider all possible pairs of elements in the set. For a set with n elements, there are n(n-1) possible pairs.
2. For each pair (a, b), there are three possibilities:
a. Both (a, b) and (b, a) are in R (only if a = b).
b. Neither (a, b) nor (b, a) is in R.
c. Either (a, b) is in R and (b, a) is not in R, or (b, a) is in R and (a, b) is not in R (only if a ≠ b).
3. Since option (a) can only occur for pairs with identical elements (a = b), there are n ways to choose such pairs.
4. For each of the other n(n-1) - n pairs, we have two options (b and c) to choose from.
Therefore, the total number of anti-symmetric relations on a set with n elements is given by:
n + 2^(n(n-1) - n)
For example, if we have a set with 3 elements, the total number of anti-symmetric relations is:
3 + 2^(3(3-1) - 3) = 3 + 2^3 = 3 + 8 = 11.