Question

The number of relations, which are both reflexive and symmetric but not anti-symmetric, on a set with 6 elements

Answer 1

Answer:

2¹⁵ - 1 = 32767

Hello.  I hope this helps you.

Step-by-step explanation:

Consider a 6×6 array with rows and columns labelled by the 6 elements in the same order.  For any two elements a, b from the set of 6, there is an entry at row a, column b.  Let this entry be 1 if a and b are related, and 0 otherwise.

The relation is reflexive if and only if the 6 entries on the principal diagonal are all 1.  Since our relation is to be reflexive, these entries must be 1.

The relation is symmetric if and only if the array is symmetric about the principal diagonal.  Since our relation is to be symmetric, the entries below the diagonal are determined by the entries above the diagonal.

So we only need to think about how many ways we can put 0s and 1s in the 5 + 4 + 3 + 2 + 1 = 15 positions above the diagonal.

As there are 15 entries and 2 choices for each of them, there are 2¹⁵ = 32768 ways to fill them.

But the relation will be anti-symmetric if and only if all the entries above the diagonal are 0.  Since we don't want to count this one, the anti-symmetric one, we exclude it.

So the number of reflexive, symmetric relations that are not anti-symmetric is 2¹⁵ - 1 = 32767.