×

Counting transitive relations. (English) Zbl 1071.06003

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.

MSC:

06A07 Combinatorics of partially ordered sets
05A17 Combinatorial aspects of partitions of integers
05A15 Exact enumeration problems, generating functions

Software:

OEIS; nauty
PDFBibTeX XMLCite
Full Text: EuDML EMIS

Online Encyclopedia of Integer Sequences:

The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambiguous.
a(n) is the number of partitions of n (the partition numbers).
a(n) = Sum_{k=0..n} p(k) where p(k) = number of partitions of k (A000041).
Powers of 2: a(n) = 2^n.
Number of graphs on n unlabeled nodes.
Bell or exponential numbers: number of ways to partition a set of n labeled elements.
Number of partially ordered sets (”posets”) with n unlabeled elements.
Number of unlabeled simple digraphs with n nodes.
Number of binary relations on n unlabeled points.
Number of symmetric relations on n nodes.
Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.
Number of partially ordered sets (”posets”) with n labeled elements (or labeled acyclic transitive digraphs).
Number of oriented graphs (i.e., digraphs with no bidirected edges) on n unlabeled nodes. Also number of complete digraphs on n unlabeled nodes. Number of antisymmetric relations (i.e., oriented graphs with loops) on n unlabeled nodes is A083670.
a(n) = 2^(n^2).
a(n) = 2^(n*(n-1)/2).
Number of transitive relations on n labeled nodes.
a(n) = 3^((n^2-n)/2).
a(n) = 2^(n^2 - n).
Number of antisymmetric binary relations on a set of n labeled points.
Number of different antisymmetric relations on n unlabeled points.
Number of antisymmetric transitive binary relations on n labeled points.
Number of automorphism groups of partial orders on n points.
Start with 10000 = DIX MILLE in French; to get the next term, replace each single letter with its equivalent Roman number if there is one; read the new number in French and repeat.
Number of idempotent relations on n labeled elements.