Number of relations
Task number: 3369
Determine the number of relations on four (\(n\)) elements:
– all,
– reflexive,
– symmetric,
– antisymmetric.
Solution
We can represent relations using an adjacency matrix \(n\times n\) containing ones and zeros. This matrix has \(n^2\) elements.
If we are counting all relations, we can choose these \(n^2\) elements arbitrarily.
For reflexive relations the diagonal must contain ones, and we can choose the remaining \(n^2-n\) elements arbitrarily.
For symmetric relations, elements that are symmetric with respect to the diagonal must be the same, so it suffices to choose elements on the diagonal and above it, and then we can fill in elements below the diagonal symmetrically.
For antisymmetric relations we must distinguish elements on the diagonal from pairs of numbers positioned symmetrically about the diagonal. Elements on the diagonal can take on two possible values, whereas for each symmetric pair there are three possibilites: both are 0; the value below the diagonal is 0 and the value above is 1; and conversely (both elements in the pair cannot be 1 simultaneously).
Answer
The total number of relations is \(2^{n^2}\), which for \(n=4\) gives \(2^{16}=65536\).
The number of reflexive relations is \(2^{n^2-n}\), which for \(n=4\) gives \(2^{12}=4096\).
The number of symmetric relations is \(2^{\frac{n^2+n}2}\), which for \(n=4\) gives \(2^{10}=1024\).
The number of antisymmetric relations is \(2^n\cdot 3^{\frac{n^2-n}2}\), which for \(n=4\) gives \(2^4{\cdot} 3^6=16{\cdot} 729=11664\).
