How to count the number of binary relations over a set of size 'n' such that they are symmetric, transitive, but not an equivalence relation (i.e. they are not reflexive).
Any help is appreciated.
Thank you.
Symmetric,transitive but not equivalence relation.
discrete mathematicsequivalence-relations
Best Answer
Suppose you have a symmetric and transitive relation $R$ on $X$. Then it is fairly straightforward to show that if you define $R_0 := \{ x \in X \mid (x, x) \in R \}$, then $R \subseteq R_0 \times R_0$, and $R$ is an equivalence relation on $R_0$. Conversely, if you have some subset $Y \subseteq X$ and some equivalence relation $S$ on $Y$, then $S$ as a subset of $X \times X$ is symmetric and transitive.
For this reason, a symmetric and transitive relation on $X$ is often called a partial equivalence relation, since we've shown that a partial equivalence relation on $X$ is equivalent to an equivalence relation on some subset $Y \subseteq X$.
Now, the problem of counting the equivalence relations on a finite set is well studied: the number of equivalence relations on a set of size $n$ is called the $n$th Bell number, $B_n$. And then, from the preceding discussion, the number of partial equivalence relations on a set of size $n$ would be equal to $$\sum_{k=0}^n \binom{n}{k} B_k.$$ This is because for each $k$, we can choose a subset $Y$ of size $k$ in $\binom{n}{k}$ ways, and then we can choose the equivalence relation on $Y$ in $B_k$ ways. However, by a well-known recurrence relation on Bell numbers, this sum is precisely equal to $B_{n+1}$.
And finally, if we want the number of symmetric and transitive relations which are not reflexive, this is equivalent to the number of partial equivalence relations which are not also equivalence relations, which would be $B_{n+1} - B_n$.
By tracing through the proofs, we can give a fairly straightforward explicit bijection between the set of partial equivalence relations on $\{ 1, \ldots, n \}$ and the set of equivalence relations on $\{ 1, \ldots, n, n+1 \}$. Namely, given a partial equivalence relation $R$ on $\{ 1, \ldots, n \}$, we can define an equivalence relation $S$ on $\{ 1, \ldots, n+1 \}$ by extending $R$ with an equivalence class equating all elements of $\{ 1, \ldots, n \} \setminus R_0$ with $n+1$. More formally, $$S := \{ (i, j) \in \{ 1, \ldots, n+1 \} \times \{ 1, \ldots, n+1 \} \mid (i, j) \in R \lor [(i, i) \notin R \wedge (j, j) \notin R] \}.$$ And for the reverse direction, given an equivalence relation $S$ on $\{ 1, \ldots, n+1 \}$, form a partial equivalence relation $R$ on $\{ 1, \ldots, n \}$ by removing the equivalence class of $n+1$. More formally, $$R := \{ (i, j) \in \{ 1, \ldots, n \} \times \{ 1, \ldots, n \} \mid (i, j) \in S \wedge (i, n+1) \notin S \}.$$