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

\[\left| {A \times B} \right| = \left| A \right| \times \left| B \right| = nm.\]

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

\[{2^{\left| {A \times B} \right|}} = {2^{nm}}.\]

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

\[{2^{{n^2} - n}} = {2^{n\left( {n - 1} \right)}}\]

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.

An example of matrix representing a symmetric relation. — Figure 1.

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

\[{2^n} \cdot {2^{\frac{{{n^2} - n}}{2}}} = {2^{n + \frac{{{n^2} - n}}{2}}} = {2^{\frac{{{n^2} + n}}{2}}} = {2^{\frac{{n\left( {n + 1} \right)}}{2}}} = \sqrt {{2^{n\left( {n + 1} \right)}}} .\]

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

\[{2^n} \cdot {3^{\frac{{{n^2} - n}}{2}}} = {2^n}\sqrt {{3^{n\left( {n - 1} \right)}}} .\]

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

\[\sqrt {{3^{n\left( {n - 1} \right)}}} .\]

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.

\[T_0 = 1,\;\;T_1 = 2,\;\;T_2 = 13,\;\;T_3 = 171,\;\;T_4 = 3994.\]

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

\[{B_0} = 1,\;\;{B_1} = 1,\;\;{B_2} = 2,\;\;{B_3} = 5,\;\;{B_4} = 15.\]

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

\[\left\{ {\left\{ a \right\},\left\{ b \right\},\left\{ c \right\}} \right\},\]

\[\left\{ {\left\{ {a,b} \right\},\left\{ c \right\}} \right\},\]

\[\left\{ {\left\{ {a,c} \right\},\left\{ b \right\}} \right\},\]

\[\left\{ {\left\{ a \right\},\left\{ {b,c} \right\}} \right\},\]

\[\left\{ {\left\{ {a,b,c} \right\}} \right\}.\]

Bell numbers can be computed using the following recursive equation:

\[{B_{n + 1}} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right){B_k}}, \]

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

\[{P_0} = 1,\;\;{P_1} = 1,\;\;{P_2} = 3,\;\;{P_3} = 19,\;\;{P_4} = 219.\]

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!\)

See solved problems on Page 2.

Calculus

Set Theory