# How many idempotent relations are there on an $n$-element set?

As far as I know, it is an open problem to give a formula counting transitive relations on an $n$-element set. Is it easier to count the idempotent relations, that is relations that are both transitive and interpolative? (A relation $\rho$ is interpolative when $x\rho y\implies((\exists z)\ x\rho z \wedge z\rho y).$)

Also, if we denote the number of transitive relations on an $n$-element set by $T_n$ and the number of idempotent relations by $I_n$, can we say what the asymptotic behavior of $I_n/T_n$ is?

-

The answer seems to be in Butler, K. K.-H.,The number of idempotents in (0,1)-matrix semigroups, Linear Algebra and Its Applications 5 (1972), 233–246. I will see if I have access to the journal and will tell you more.

Edit. The paper is here for free. It counts the idempotents by D-class so it is not written down in a simple succinct formula. If you google idempotent boolean matrix there are further papers which may be of use.

-
This is the answer to your first question. I don't know about the second one. –  Benjamin Steinberg Feb 27 '13 at 14:03
Thank you very much. I made a mistake in the second question. I've changed "interpolative" to "idempotent" now. –  Michał Masny Feb 27 '13 at 18:57