Counting Relations

Home → 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 \times B.\) If these sets are finite and have cardinality \(\left| A \right| = n\) and \(\left| B \right| = 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 \times 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.

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