# Counting Relations

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

How many relations are there on a set of \(n\) elements that are reflexive and symmetric?

### Example 2

How many relations are there on a set of \(n\) elements that are reflexive and antisymmetric?

### Example 3

How many relations are there on a set of \(n\) elements that are neither reflexive nor irreflexive?

### Example 4

How many relations are there on a set of \(n\) elements that are neither symmetric nor antisymmetric?

### Example 5

Let \(B = \left\{ {0,1} \right\}.\) How many relations on the set \(B\) are not symmetric?

### Example 6

Let \(A = \left\{ {a,b,c} \right\}.\) How many relations on the set \(A\) are reflexive, symmetric, and not transitive?

### Example 1.

How many relations are there on a set of \(n\) elements that are reflexive and symmetric?

Solution.

Consider a set \(A\) consisting of \(n\) elements and a relation \(R.\) Since \(R\) is reflexive, its binary matrix must contain the diagonal elements \(\left( {a,a} \right)\) for every \(a \in A.\)

The number of remaining off-diagonal elements is equal to \(n^2 - n.\) If the relation \(R\) is symmetric and has a non-diagonal element \(\left( {a,b} \right)\) where \(a \ne b,\) then it also includes the opposite element \(\left( {b,a} \right).\) It is clear that it is enough to consider all options in the left lower (or in the right upper) triangle of the matrix. Each of the triangles contains \(\frac{{{n^2} - n}}{2}\) elements.

Hence, there are

relations on the set \(A\) that are simultaneously reflexive and symmetric.

### Example 2.

How many relations are there on a set of \(n\) elements that are reflexive and antisymmetric?

Solution.

If a relation \(R\) on set \(A\) is reflexive, its matrix must include the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\) We do not count these elements.

The number of the remaining off-diagonal elements is equal to \(n^2 - n.\) These elements form the pairs \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) where \(a \ne b.\) Total there are \(\frac{{{n^2} - n}}{2}\) such pairs.

There are \(3\) possible options for each pair. We can choose either \({\left( {a,b} \right)}\) or \({\left( {b,a} \right)},\) or none of them.

Consequently, there are

elations that are reflexive and antisymmetric.

### Example 3.

How many relations are there on a set of \(n\) elements that are neither reflexive nor irreflexive?

Solution.

A relation \(R\) on a set \(A\) is reflexive if it contains all diagonal elements of kind \(\left( {a,a} \right)\) where \(a \in A.\) There are \({2^{{n^2} - n}}\) distinct reflexive relations on the set \(A.\)

Similarly, if \(R\) is irreflexive it does not include the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\) The number of irreflexive relations is the same and equal to \({2^{{n^2} - n}}.\)

Given the the total number of relations is \({2^{{n^2}}},\) we find the number of relations \(N\) that are neither reflexive nor irreflexive:

### Example 4.

How many relations are there on a set of \(n\) elements that are neither symmetric nor antisymmetric?

Solution.

Both symmetric and antisymmetric relations have no restrictions on the diagonal elements \(\left( {a,a} \right)\) for all \(a \in A.\)

As for the off-diagonal elements, symmetric and antisymmetric relations have mutually exclusive requirements. For a symmetric relation, both elements of a pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\}\) where \(a \ne b,\) must belong to the relation. An antisymmetric relation may have either one element of a pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) or none of them.

Therefore, the relations that are neither symmetric nor antisymmetric may contain only diagonal elements. There are \(2^n\) such relations.

### Example 5.

Let \(B = \left\{ {0,1} \right\}.\) How many relations on the set \(B\) are not symmetric?

Solution.

The total number of relations on a set of \(2\) elements is

The number of symmetric relations on the set is given by

Then there are \(16-8=8\) relations on set \(B = \left\{ {0,1} \right\}\) that are not symmetric. These relations are shown in figure below.

### Example 6.

Let \(A = \left\{ {a,b,c} \right\}.\) How many relations on the set \(A\) are reflexive, symmetric, and not transitive?

Solution.

If we consider only reflexive and symmetric relations, there are

such relations.

Recall that if a relation is reflexive, symmetric, and transitive, it is called an equivalence relation. The set \(A\) of \(3\) elements contains \(B_3 = 5\) equivalence relations.

Hence, the number of relations that are reflexive, symmetric, but not transitive is equal to

These \(3\) relations look as follows: