MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
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

See OEIS sequence A121337 and references given there.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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