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.

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.