Götz Pfeiffer,
# Counting Transitive Relations.

*J. Integer Seq.* **7** (2004), no. 3, Article 04.3.2, 11 pages.
(electronic).

## Abstract.

In order to count partial orders on a set of $n$ points, it
seems necessary to explicitly construct a representative of every
isomorphism type. While that is done, one might as well determine
their automorphism groups. In this note it is shown how several other
types of binary relations can be counted, based on an explicit
enumeration of the partial orders and their automorphism groups. A
partial order is a transitive, reflexive, and antisymmetric binary
relation. Here we determine the number of quasi-orders
$q(n)$ (or finite topologies or transitive digraphs or
transitive reflexive relations), the number of "soft" orders
$s(t)$ (or transitive antisymmetric relations), and the
number of transitive relations $t(n)$ on $n$
points in terms of numbers of partial orders with a given automorphism
group.
Available as DVI file (85 kB)
plus a figure (5 kB),
as pdf file (163 kB)
and as
compressed PostScript (151 kB) file.