Geodesic
Counting transitive relations
Journal of integer sequences, Tome 7 (2004) no. 3.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 reflexive transitive relations), the number of "soft" orders $s(t)$ (or antisymmetric transitive relations), and the number of transitive relations $t(n)$ on $n$ points in terms of numbers of partial orders with a given automorphism group.
Classification : 05A15, 06A07
Keywords: binary relation, partial order, quasi-order, soft order, transitive relation, symmetric group, group action, finite topology, automorphism group, enumeration 
@article{JIS_2004__7_3_a6,
     author = {Pfeiffer, G\"otz},
     title = {Counting transitive relations},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {7},
     number = {3},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2004__7_3_a6/}
}
TY  - JOUR
AU  - Pfeiffer, Götz
TI  - Counting transitive relations
JO  - Journal of integer sequences
PY  - 2004
VL  - 7
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2004__7_3_a6/
LA  - en
ID  - JIS_2004__7_3_a6
ER  - 
%0 Journal Article
%A Pfeiffer, Götz
%T Counting transitive relations
%J Journal of integer sequences
%D 2004
%V 7
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2004__7_3_a6/
%G en
%F JIS_2004__7_3_a6
Pfeiffer, Götz. Counting transitive relations. Journal of integer sequences, Tome 7 (2004) no. 3. http://geodesic.mathdoc.fr/item/JIS_2004__7_3_a6/