I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one.
I've counted 7: {$(1,1)$} , {$(2,2)$} , {$(3,3)$} , {$(1,2),(2,1)$}, {$(1,3),(3,1)$}, {$(2,3), (3,2)$}, {$(1,2),(2,1), (1,3),(2,3) (3,1), (3,2)$}.
Thanks.
The number of symmetric and transitive relations on $n$ things is the number of reflexive, symmetric and transitive relations on $n+1$ things. Given a symmetric and transitive relation $R$ on $\{\,1,2,\dots,n\,\}$, chuck in $(n+1,n+1)$, and $(a,n+1)$ and $(n+1,a)$ and $(a,a)$ for every $a$ such that $(a,a)$ is not in $R$; that gives a reflexive, symmetric and transitive relation on $\{\,1,2,\dots,n+1\,\}$.
The number of reflexive, symmetric and transitive relations is the number of partitions, which is counted by the Bell numbers, which are tabulated at https://oeis.org/A000110 --- there is a huge literature about these numbers.