# Counting Relations

In this lesson, we will be looking at counting relations with different properties.

Recall that a binary relation *R* from set *A* to set *B* is defined as a subset of the Cartesian product *A* × *B*. If these sets are finite and have cardinality |*A*| = *n* and |*B*| = *m*, then the cardinality of their Cartesian product is given by

Hence, the number of subsets of *A* × *B* or the number of relations from *A* to *B* is

In particular, the number of relations defined on one set *A* of cardinality *n* is equal to \({2^{{n^2}}}.\)

Binary relations may have different properties such as reflexivity, symmetry, transitivity and so on. Further, we consider how many relations of different type exist on a set *A* consisting of *n* elements.

## Reflexive Relations

A reflexive relation on set \(A\) must contain the \(n\) elements \(\left( {a,a} \right)\) for every \(a \in A.\) The remaining number of pairs is \(n^2 - n.\) So we can choose only among \(n^2 - n\) elements to build reflexive relations. Hence, there are

reflexive relations on a set with cardinality \(n.\)

An irreflexive relation is the opposite of a reflexive relation. It contains no identity elements \(\left( {a,a} \right)\) for all \(a \in A.\) It is clear that the total number of irreflexive relations is given by the same formula as for reflexive relations.

## Symmetric Relations

As we know a binary relation corresponds to a matrix of zeroes and ones. A symmetric relation is described by a symmetric matrix such as the one in figure below.

In a symmetric matrix, \(a_{ij} = a_{ji}.\) So choosing a value for an element in the left lower triangle determines the corresponding element in the right upper triangle. The number of the off-diagonal elements is \(n^2 - n.\) Respectively, the number of elements in the lower or upper triangle is equal to \(\frac{{{n^2} - n}}{2}.\) Hence, there are \({2^{\frac{{{n^2} - n}}{2}}}\) ways to set the off-diagonal elements in the relation. Besides that, there are \(2^n\) ways to set diagonal elements that may take any values. Therefore, the total number of symmetric relations on a set with cardinality \(n\) is defined by the formula

## Antisymmetric Relations

Antisymmetric relations have no restrictions on the diagonal elements \(\left( {a,a} \right),\) so there are \(2^n\) ways to set such elements. As to the non-diagonal elements, there are \(3\) options for each pair \(\left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\) where \(a \ne b.\) An antisymmetric relation may contain either \({\left( {a,b} \right)}\) or \({\left( {b,a} \right)},\) or none of them. Therefore, there are \({3^{\frac{{{n^2} - n}}{2}}}\) ways to set the off-diagonal elements. The total number of antisymmetric relations is given by the expression

## Asymmetric Relations

A binary relation is called asymmetric if it is both antisymmetric and irreflexive. Thus an asymmetric relation does not contain the diagonal elements \(\left( {a,a} \right).\) The total number of asymmetric relations on a set with \(n\) elements is expressed by the formula

## Transitive Relations

Finding the number of transitive relations on a set with \(n\) elements is not a simple problem. As of \(2020,\) there is no known closed-form formula to count the number of transitive relations. Of course, such calculations can be performed numerically. The sequence OEIS A006905 thus defined describes the number of transitive relations \(T_n\) on a finite set with cardinality \(n.\) The first few values in this sequence are listed below.

## Equivalence Relations

The number of equivalence relations on a set is equal to the number of partitions. These numbers are known as Bell numbers. The first few Bell numbers are given by

For example, the set \(A = \left\{ {a,b,c} \right\}\) consists of \(3\) elements and therefore has \(B_3 = 5\) partitions:

Bell numbers can be computed using the following recursive equation:

where \(\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right)\) are the binomial coefficients.

## Partial Orders

Similarly to transitive relations, there is no closed formula to count the number of partial orders on a set. This number is represented by the sequence OEIS A001035. The first several values are

## Total Orders

The number of total orders on a set of cardinality \(n\) is equal to the number of permutations on the set. Hence, the number of total orders is \(n!\)