2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What have you counted 7? {(1,2),(2,1)} is symmetric. But if it were transitive, then it should also contain (1,1) and (2,2). $\endgroup$ – Swapniel Apr 7 '14 at 10:18
  • $\begingroup$ Sorry, my mistake. I counted them again and I found 7. $\endgroup$ – ruplop Apr 8 '14 at 0:37
  • $\begingroup$ This one is symmetric and transitive, right? {$(1,1),(1,3),(3,1),(3,3),(2,2)$} $\endgroup$ – ruplop Apr 9 '14 at 0:47
  • $\begingroup$ Yes it is symmetric and transitive. $\endgroup$ – Swapniel Apr 9 '14 at 16:17
  • $\begingroup$ Asked again, a couple of days later: math.stackexchange.com/questions/745923/… $\endgroup$ – Gerry Myerson Apr 10 '14 at 11:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.