\documentclass[12pt,reqno]{article}
\usepackage
[colorlinks=true,
linkcolor=green,
filecolor=brown,
citecolor=green]{hyperref}
\usepackage{color}
\usepackage{fullpage}
%\usepackage[fancy]{rcsinfo}
%\rcsInfo $Id: posetseq.tex,v 1.36 2004/07/09 12:40:19 goetz Exp $
\usepackage{psfig}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{array} % provides '\extrarowheight'
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\usepackage[mathcal]{euler}
\usepackage{epsfig}
\title{Counting Transitive Relations.}
\author{G\"otz Pfeiffer}
%\date{\rcsInfoDate\ (Version \rcsInfoRevision)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Size}[1]{\left|#1\right|}
\newcommand{\Sub}{\mathsf{Sub}}
\newcommand{\Sym}{\mathsf{Sym}}
\newcommand{\Aut}{\mathsf{Aut}}
\newcommand{\rta}{\mathsf{rta}}
\newcommand{\RTA}{\mathsf{RTA}}
\newcommand{\ta}{\mathsf{ta}}
\newcommand{\TA}{\mathsf{TA}}
\newcommand{\rt}{\mathsf{tr}}
\newcommand{\RT}{\mathsf{TR}}
\renewcommand{\t}{\mathsf{t}}
\newcommand{\T}{\mathsf{T}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\QQ}{\mathcal{Q}}
\newcommand{\RR}{\mathcal{R}}
\let\oldSS\SS\let\SS\relax
\newcommand{\SS}{\mathcal{S}}
\newcommand{\TT}{\mathcal{T}}
\newcommand{\range}[2]{\{#1,\ldots,#2\}}
\newcommand{\stirling}[2]{\left\{#1 \atop #2\right\}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{Theorem}{Theorem}
\newtheorem{Lemma}{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf Counting Transitive Relations
}
\vskip 1cm
\large
G\"otz Pfeiffer\\
Department of Mathematics\\
National University of Ireland, Galway\\
Ireland\\
\href{mailto:goetz.pfeiffer@nuigalway.ie}{\tt goetz.pfeiffer@nuigalway.ie} \\
\end{center}
%\maketitle
\begin{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
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.
%\renewcommand{\thefootnote}{}\footnote{\rcsInfoDate\ (Version \rcsInfoRevision)}
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction.} \label{sec:intro}
A \emph{partial order} on a set $X$ with $n$ elements is a binary relation on
$X$ which is transitive, reflexive and antisymmetric. We denote by $P(n)$
the number of different partial orders on $n$ labelled points (sequence
\seqnum{A001035}), and by $p(n)$ the number of partial orders on $n$
unlabelled points (sequence \seqnum{A000112}).
In this note we assume the
numbers $P(n)$ and $p(n)$ to be available. For $p(n)$ we even assume the
availability of an explicit list, or an enumeration procedure like the ones
developed by Heitzig and Reinhold~\cite{Heitzig00}, or more recently by
Brinkmann and McKay~\cite{Brinkmann02}. From the latter article, $p(n)$ is
known for $n \leq 16$ and $P(n)$ is known for $n \leq 18$.
A ``labelled'' binary relation on $X$ is a set of pairs $R \subseteq X \times
X$. If the actual names of the points being related are of no importance we
talk about ``unlabelled'' binary relations. Technically, these are orbits of
the action of the symmetric group $\Sym(X)$ on $X \times X$. Here the image
of a binary relation $R$ on $X$ under a permutation $\alpha \in \Sym(X)$ is
the relation $R.\alpha = \{(x.\alpha, y.\alpha) \mid (x, y) \in R\}$.
\begin{figure}[htbp]
\centering
\epsfig{file=rstai.0, width=.5\textwidth}
\caption{Different types of binary relations.}
\label{fig:rstai}
\end{figure}
Figure~\ref{fig:rstai} shows the different kinds of binary relations that can
be defined in terms of the properties reflexive (R), symmetric (S),
transitive (T), antisymmetric (A), irreflexive~(I), and all possible
combinations thereof. Clearly no relation on $n > 0$ points can be both
reflexive and irreflexive. The shaded areas indicate other impossible
combinations: transitive and irreflexive implies antisymmetric; antisymmetric
and symmetric implies transitive. The dotted areas indicate singleton sets:
the only antisymmetric equivalence relation on $n > 0$ points is the identity
relation; the only irreflexive transitive relation on $n > 0$ points which is
both symmetric and antisymmetric is the empty relation.
Partial orders are particularly difficult to enumerate, be it labelled or
unlabelled.
%
Table~\ref{tab:numbers} lists the different kinds of relations together with
formulas and references to integer sequences (from the Online Encyclopedia of
Integer Sequences~\cite{oeis}) for the numbers of such relations, both
labelled and unlabelled. The numbers of many kinds of labelled binary
relations are given by simple formulas. Kinds of irreflexive relations (if
they exist) have the same number formulas as the corresponding reflexive
kinds and therefore have been left out. The terms $Q(n)$, $S(n)$, $T(n)$,
and their lowercase counterparts will be introduced below, $E(n)$ denotes the
number of equivalence relations on $n$ points, a sequence known as the Bell
numbers, and $e(n)$ is the number of partitions of $n$. Classical sources
for some of these sequences and the formulas relating them are for example
the books by Harary and Palmer~\cite{HararyPalmer}, or by Graham, Knuth and
Patashnik~\cite{GKP}. Some types of unlabelled binary relations can be
easily enumerated with the help of P\'olya theory, a group theoretical
technique that translates the orbit counting problem into a problem of
counting fixed points (see for example \cite{Oberschelp}). The problem of
counting the types of transitive relations does not seem to have received
much attention so far.
\begin{table}[htbp]
\centering \extrarowheight1ex
\let\R\relax\newcommand{\R}{\phantom{R}}
\let\S\relax\newcommand{\S}{\phantom{S}}
\let\T\relax\newcommand{\T}{\phantom{T}}
\let\A\relax\newcommand{\A}{\phantom{A}}
\begin{tabular}[htbc]{clll} \hline
Properties &$\#$ Labeled Relations & \multicolumn{2}{l}{$\#$ Unlabeled Relations on $n$ points} \\ \hline
(none) & $\strut 2^{n^2} =\ $\seqnum{A002416}$(n)$ & \seqnum{A000595}$(n)$ & all relations \\
R\S\T\A & $4^{\binom{n}2} =\ $\seqnum{A053763}$(n)$ & \seqnum{A000273}$(n)$ & reflexive \\
\R S\T\A & $2^{\binom{n+1}2} =\ $\seqnum{A006125}$(n{+}1)$ & \seqnum{A000666}$(n)$ & symmetric \\
\R\S T\A & $T(n) =\ $\seqnum{A006905}$(n)$ & $t(n) =\ $\seqnum{A091073}$(n)$ & transitive \\
\R\S\T A & $2^n 3^{\binom{n}2} =\ $\seqnum{A083667}$(n)$ & \seqnum{A083670}$(n)$ & antisymmetric \\
RS\T\A & $2^{\binom{n}2} =\ $\seqnum{A006125}$(n)$ & \seqnum{A000088}$(n)$ & simple graphs \\
R\S T\A & $Q(n) =\ $\seqnum{A000798}$(n)$ & $q(n) =\ $\seqnum{A001930}$(n)$ & quasi-orders \\
R\S\T A & $3^{\binom{n}2} =\ $\seqnum{A047656}$(n)$ & \seqnum{A001174}$(n)$ & \\
\R ST\A & $E(n{+}1) =\ $\seqnum{A000110}$(n{+}1)$ & $e(0) + \dots + e(n) =\ $\rlap{\seqnum{A000070}$(n)$} & \\
\R\S TA & $S(n) =\ $\seqnum{A091566}$(n)$ & $s(n) =\ $\seqnum{A079265}$(n)$ & soft orders \\
RST\A & $E(n) =\ $\seqnum{A000110}$(n)$ & $e(n) =\ $\seqnum{A000041}$(n)$ & equivalences \\
R\S TA & $P(n) =\ $\seqnum{A001035}$(n)$ & $p(n) =\ $\seqnum{A000112}$(n)$ & partial orders \\
\R STA & $2^n =\ $\seqnum{A000079}$(n)$ & $n{+}1 =\ $\seqnum{A000027}$(n{+}1)$ & subsets \\
\hline
\end{tabular}
\caption{Numbers of binary relations.}
\label{tab:numbers}
\end{table}
However, 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.
This is the point of view taken here. 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. More
precisely, 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(n)$ (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.
\textbf{Quasi-Orders.} A binary relation $\preceq$ on $X$ that is only
required to be transitive and reflexive is called a \emph{quasi-order}. Such
a relation may allow both $x \preceq y$ and $y \preceq x$ to hold for certain
pairs $x, y \in X$. But then, the \emph{symmetric core} $\equiv$ of
$\preceq$, defined by
\begin{equation} \label{symcore}
x \equiv y \text{ if and only if } x \preceq y \text{ and } y \preceq x,
\end{equation}
clearly is an equivalence relation on $X$. Moreover, $\preceq$ can be used
to define a relation $\sqsubseteq$ on the quotient set $X/{\equiv}$ of
equivalence classes $[x] = \{y \in X : x \equiv y\}$ as
\begin{equation} \label{quasi}
[x] \sqsubseteq [y] \text{ if and only if } x \preceq y.
\end{equation}
Clearly, the relation $\sqsubseteq$ is a partial order on $X/{\equiv}$.
Conversely, given an equivalence relation $\equiv$ on $X$ together with a
partial order $\sqsubseteq$ on the equivalence classes $X/{\equiv} = \{[x] :
x \in X\}$, condition (\ref{quasi}) defines a quasi-order $\preceq$ on $X$.
Thus a quasi-order on $X$ is a partition $L$ of $X$ together with a partial
order on $L$. If we denote by $\PP(S)$ the set of partial orders on a set
$S$, by $\QQ(X)$ the set of quasi-orders on $X$, and by $\Lambda(X, k)$ the
set of partitions of $X$ into $k$ nonempty parts $L_1, \dots, L_k$, then
\begin{equation}
\label{eq:nrquasi}
\# \QQ(X) = \sum_k \sum_{L \in \Lambda(X, k)} \#\PP(L)
= \sum_k P(k)\;\#\Lambda(X, k).
\end{equation}
We denote by $Q(n)$ the number of labelled quasi-orders on $n$ points
(sequence \seqnum{A000798}) and by $q(n)$ the number of unlabelled
quasi-orders on $n$ points (sequence \seqnum{A001930}). The number of
partitions of a set $X$ of size $\Size{X} = n$ into $k$ nonempty parts is
given by a Stirling number of the second kind,
\begin{equation} \label{eq:stirling}
\Size{\Lambda(X, k)} = \stirling{n}{k}.
\end{equation}
It follows that the total number $Q(n)$ of reflexive transitive relations on
$n$ labelled points can be expressed in terms of the numbers $P(k)$ of
labelled partial orders on $k$ points as
\begin{equation}
Q(n) = \sum_k \stirling{n}{k} P(k).
\end{equation}
Thus the sequence $Q(n)$ is the \emph{Stirling transform} of the sequence
$P(n)$, just like $E(n) = \sum_k \stirling{n}{k}$ is the Stirling transform
of the constant $1$-sequence. In section~\ref{sec:trans} we derive a formula
that allows us to calculate the number $q(n)$ of quasi-orders on $n$
unlabelled points up to $n = 12$.
A quasi-order $\preceq$ on a finite set $X$ defines on $X$ a topological
structure: the open sets are the order ideals $\{y \in X \mid x \preceq y\}$.
Conversely, a topology on a finite set $X$ defines a quasi-order $\preceq$
via
\begin{equation}
x \preceq y \text{ if and only if every open set that contains }
x \text{ also contains } y.
\end{equation}
Thus the number of types of topologies on $n$ points is given by $q(n)$ as
well. The Encyclopedia~\cite{oeis} currently lists the values $q(n)$ for $n
\leq 7$.
\textbf{Soft Orders.} Let us call a binary relation $\preceq$ on $X$ that is
only required to be transitive and antisymmetric a \emph{soft order}. (There
does not seem to be a particular name for this kind of relation in widespread
use. I suggest to use the term ``soft order'' for a partial order that is
soft on the reflexive condition.) Every soft order $\preceq$ on $X$
determines a partial order on $X$ (as its reflexive closure) and a subset
\begin{equation}
Y = \{x \in X \mid x \npreceq x\}
\end{equation}
of \emph{irreflexive points}. Conversely,
every partial order on a set $X$ together with a subset $Y \subseteq X$
determines a soft order on $X$.
Thus a soft order on $X$ is a partial order on $X$ together with a
distinguished subset $Y \subseteq X$ of irreflexive elements. If we denote
by $2^X$ the power set of $X$ and by $\SS(X)$ the set of soft orders on $X$
then
\begin{equation}
\label{eq:nrsoft}
\#\SS(X) = \#(2^X \times \PP(X)) = \#2^X\; \#\PP(X).
\end{equation}
We denote by
$S(n)$ the number of labelled soft orders on $n$ points (sequence
\seqnum{A091566}) and by $s(n)$ the number of unlabelled soft orders on $n$
points (sequence \seqnum{A079265}). It follows that
\begin{equation}
S(n) = 2^n\, P(n).
\end{equation}
% The numbers $s(n)$ are listed up to $n = 9$.
In section~\ref{sec:trans} we derive a formula that allows us to calculate
$s(n)$ up to $n = 12$.
Binary relations of this type have been introduced by Taylor and
Hilton~\cite{Taylor1981} as structure diagrams of balanced complete
experimental designs. There they are also known as mixed models. The values
$s(n)$ for $n \leq 9$ are listed on Lygeros' web page~\cite{Lygeros}.
\textbf{Transitive Relations.} Assume $X \cap 2^X = \emptyset$. Let us call
a set $A$ an \emph{augmented partition} of $X$, if for $Y = A \cap X$ the set
$A \setminus Y$ is a partition of the set $X \setminus Y$. Then an augmented
partition of $X$ is the union of a subset $Y \subseteq X$ and a partition of
its complement $X \setminus Y$.
Given a transitive relation $\preceq$ on $X$, let $Y = \{x \in X \mid x
\npreceq x\}$ be its set of irreflexive points. Then the symmetric core
$\equiv$ (defined by $x \equiv y$ if and only if $x \preceq y$ and $y \preceq
x$) is an equivalence relation on $X \setminus Y$, since $x \equiv y$ implies
$x \preceq x$ (and $y \preceq y$) for all $x, y \in X$. Denote by
$X/\!/{\equiv}$ the resulting augmented partition ${(X\setminus Y)/{\equiv}}
\;\cup\; Y$ of $X$. Furthermore, the relation $\preceq$ defines a partial
order $\sqsubseteq$ on $X/\!/{\equiv}$, where
\begin{equation}\label{eq:transi}
[x] \sqsubseteq [y] \text{ if and only if } x \preceq y.
\end{equation}
Here $[x]$ means the $\equiv$-class of $x$ if $x \in X \setminus Y$, and the
element $x$ if $x \in Y$.
Conversely, every choice of a subset $Y \subseteq X$, a partition $L$ of its
complement $X \setminus Y$ and a partial order $\sqsubseteq$ on the augmented
partition $L \cup Y$ yields via (\ref{eq:transi}) a transitive relation
$\preceq$ on $X$.
Thus a transitive relation on $X$ is an augmented partition $L \cup Y$ of $X$
together with a partial order on $L \cup Y$. If we denote by $\TT(X)$ the
set of transitive relations on $X$ then
\begin{equation}
\label{eq:nrtrans}
\#\TT(X) = \sum_{k=0}^n \sum_{s=0}^k \sum_Y \sum_L \#\PP(L \cup Y \}),
\end{equation}
where the sum is over all subsets $Y \in \binom{X}{s}$ and all partitions $L \in
\Lambda(X\setminus Y, k - s)$. We denote the number of labelled transitive
binary relations on $n$ points by $T(n)$ (sequence \seqnum{A006905}), and the
number of unlabelled transitive binary relations on $n$ points by $t(n)$
(sequence \seqnum{A091073}). It follows from the above
description, using $\#\PP(L \cup Y) = P(k)$, $\#
\Lambda(X\setminus Y, k - s) = \stirling{n-s}{k-s}$ and $\# \binom{X}{s} =
\binom{n}{s}$, that
\begin{equation}
T(n) = \sum_{k=0}^n \left(\sum_{s=0}^k \binom{n}{s}
\stirling{n-s}{k-s}\right) P(k),
\end{equation}
(see \cite{Klaska1997}).
In section~\ref{sec:trans} we derive a formula that allows us to
calculate $t(n)$ up to $n = 12$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Unlabelled kinds of transitive relations.} \label{sec:trans}
In this section we derive formulas for the numbers $q(n)$ of unlabelled
quasi-orders, $s(n)$ of unlabelled soft orders, and $t(n)$ of unlabelled
transitive relations on $n$ points. We begin with two general facts about
finite group actions.
\begin{Lemma}\label{la:1}
Suppose a finite group $G$ acts on finite sets $X$ and $Y$. Let $f \colon
X \to Y$ be a $G$-map, i.e., $f(x.g) = f(x).g$ for all $x \in X$, $g \in
G$. Then
\begin{equation}\label{eq:la1-1}
x.G \cap f^{-1}(y) = x.G_y
\end{equation}
for all $x \in X$, $y = f(x) \in Y$. Moreover, the number of $G$-orbits on
$X$ is given by
\begin{equation}
\# X/G = \sum_{y.G \in Y/G} \# f^{-1}(y)/G_y,
\end{equation}
where the sum is taken over representatives $y$ of $G$-orbits $y.G$ on $Y$.
\end{Lemma}
\begin{proof}
Let $H = G_y$, the stabilizer of $y$ in $G$. Clearly $x.H \subseteq x.G$.
Moreover, $H$ acts on $f^{-1}(y)$ since for $z \in f^{-1}(y)$ and $h \in H$
we have $f(z.h) = f(z).h = y.h = y$. It follows that $x.H \subseteq
f^{-1}(y)$. Conversely, let $z \in x.G \cap f^{-1}(y)$. Then $f(z) = y$
and $z = x.g$ for some $g \in G$. But $y = f(z) = f(x.g) = f(x).g = y.g$
implies $g \in G_y = H$ whence $z \in x.H$.
Now let $y \in Y$. Then by~(\ref{eq:la1-1}) the map $z.G \mapsto z.G \cap
f^{-1}(y) = z.G_y$ is a bijection between $f^{-1}(y.G)/G$ and $f^{-1}(y)/G_y$.
Moreover $X$ is the disjoint union of the sets $f^{-1}(y.G)$, where $y$
runs over a set of representatives of $G$-orbits $y.G$ on $Y$ (and
$\#\emptyset/G = 0$).
\end{proof}
\begin{Lemma}\label{la:2}
Suppose a finite group $G$ acts on finite sets $X$ and $Y$. Then the
number of $G$-orbits on the Cartesian product $X \times Y$ is given by the
formula
\begin{equation}
\#(X \times Y)/G =
\sum_{r.G \in X/G} \# Y/G_r =
\sum_{[H] \in \Sub(G)/G} m_X(H)\, \#Y/H,
\end{equation}
where the first sum is over representatives $r \in X$ of $G$-orbits $r.G$
on $X$, the second sum is over representatives $H$ of conjugacy classes
$[H]$ of subgroups of $G$ and where
\begin{equation}
m_X(H) = \# \{r.G \in X/G \mid G_r \in [H]\}
\end{equation}
is the multiplicity of $H$ as stabilizer of a $G$-orbit in $X$.
\end{Lemma}
\begin{proof}
Apply Lemma~\ref{la:1} to the projection $X \times Y \to X$.
\end{proof}
We need a bit of notation before we can formulate and prove the main
theorems. For $n \in \N_0$ we denote by $\PP(n)$ the partial orders on
$\range1n$, like we denote the symmetric group on this set by $\Sym(n)$.
And for $H \leq \Sym(n)$ we denote by $\mu_n(H)$ the number of unlabelled
partial orders $P$ on $n$ points with automorphism group $\Aut(P)$ conjugate
to $H$ in $\Sym(n)$. (More precisely, $\mu_n(H)$ is defined by the equation
$\Size{N_{\Sym(n)}(H)} \mu_n(H) = \Size{H} \nu_n(H)$, where $\nu_n(H)$ is
the number
of labelled partial orders $P$ on the $n$ points $\range1n$ with $\Aut(P) =
H$.) Let $\RR_n$ be a transversal of the conjugacy classes of subgroups of
$\Sym(n)$. Then we have
\begin{align}
p(n) &= \sum_{H \in \RR_n} \mu_n(H), &
P(n) &= \sum_{H \in \RR_n} \frac{n!}{\Size{H}} \mu_n(H)
\end{align}
for $n \geq 0$.
\begin{Theorem} \label{thm:s}
The number $s(n)$ of unlabelled soft orders on $n$ points is given by
\begin{equation}
s(n) = \sum_{H \in \RR_n} \mu_n(H)\, \# 2^X/H,
\end{equation}
where $X = \range1n$.
\end{Theorem}
\begin{proof}
We have $s(n) = \#\SS(X)/\Sym(X) = \#(\PP(X) \times 2^X)/\Sym(X)$, and by
Lemma~\ref{la:2},
\begin{equation}
\#{(\PP(X) \times 2^X)/\Sym(n)}
= \sum_{P \in \PP(X)} \#{2^X/\Aut(P)}
= \sum_{H \in \RR_n} \mu_n(H)\, \#{2^X/H},
\end{equation}
as claimed.
\end{proof}
\begin{Theorem} \label{thm:q}
The number $q(n)$ of unlabelled quasi-orders on $n$ points is given by
\begin{equation}
q(n) = \sum_{k = 1}^n \sum_{H \in \RR_k} \mu_k(H)\, \# M(k, n)/H,
\end{equation}
where $M(k, n)$ is the set of maps $\{f \colon \range1k \to \range1n \mid
f(1) + \dots + f(k) = n\}$.
\end{Theorem}
\begin{proof}
Let $X = \range1n$. The map $f \colon \QQ(X) \to \Lambda(X)$ which
associates to each quasi-order $Q \in \QQ(X)$ the partition $X/{\equiv_Q}
\in \Lambda(X)$ induced by its symmetric core ${\equiv_Q}$ on $X$ is a
$G$-map for $G = \Sym(X)$. Hence, by Lemma~\ref{la:1},
\begin{equation}
\# \QQ(X)/G = \sum_{L.G \in \Lambda(X)/G} \#f^{-1}(L)/G_L.
\end{equation}
Now let $L = \{L_1, \dots, L_k\} \in \Lambda(X)$ be a partition of $X$ into
$k$ parts. Then the stabilizer $G_L$ contains a normal subgroup $N =
\Sym(L_1) \times \dots \times \Sym(L_k)$ which lies in the kernel of the
$G_L$-action on $f^{-1}(L)$. Let $H \leq \Sym(L)$ be the group of
permutations of $L$ induced by $G_L$, i.e., $H = \{ \bar{\alpha}: L \to L
\mid \alpha \in G_L\}$ where $L_i.\bar{\alpha} = L_i.\alpha = \{j.\alpha :
j \in L_i\}$. Then $G_L/N \cong H$ and
\begin{equation}
\# f^{-1}(L)/G_L = \# f^{-1}(L)/H = \# \PP(L)/H,
\end{equation}
since the set $\PP(L)$ of partial orders on $L$ is $H$-equivalent to
$f^{-1}(L)$. Now the map $L \to \range1k$ defined by $L_i \mapsto i$
translates $\PP(L)$ into $\PP(k)$ and $H$ into a subgroup $\tilde{H}$
of $\Sym(k)$.
A \emph{composition} of $n$ is a sequence $c = (c_1, \dots, c_k)$ of
nonnegative integers $c_i$ with $c_1 + \dots + c_k = n$. The \emph{shape}
of the composition $c = (c_1, \dots, c_k)$ is the \emph{partition} $[c_1,
\dots, c_n]$ of $n$, usually written as a decreasing list of the entries in
$c$.
Here $\tilde{H}$ is the stabilizer of the composition $c = (\Size{L_1},
\dots, \Size{L_k})$ of $n$ in the action of $\Sym(k)$ on the set of all
compositions of length $k$. For a partition $\pi$ of $n$ denote by
$C(\pi)$ the set of all compositions of $n$ with shape $\pi$. Note that,
if $\pi$ is the shape of the composition $c$ then $C(\pi) = c.\Sym(k)$.
Hence applying Lemma~\ref{la:2} twice yields
\begin{equation}
\# \PP(L)/H = \# \PP(k)/\tilde{H}
= \# (\PP(k) \times C(\pi)) / \Sym(k) %\\&
%= \sum_{P.\Sym(k) \in \PP(k)/\Sym(k)} \# C(\pi)/\Aut(P)
= \sum_{U \in \RR_k} \mu_k(U)\; \# C(\pi)/U,
\end{equation}
since $\mu_k(U)$ is the multiplicity of $U$ as stabilizer of a $\Sym(k)$-orbit on
$\PP(k)$.
Finally, the map which associates to every partition $L = \{L_1, \dots,
L_k\} \in \Lambda(X)$ the partition $[\Size{L_1}, \dots, \Size{L_k}]$ of $n
= \Size{X}$ given by the sizes of the parts of $L$ is a bijection between
$\Lambda(X)/G$ and $\Pi(n)$, the set of all partitions of $n = \Size{X}$.
Thus
\begin{equation}
\# \QQ(X)/G = \sum_{\pi \in \Pi(n)} \sum_{U \in \RR_{l(\pi)}}
\mu_{l(\pi)}(U)\; \#C(\pi)/U,
\end{equation}
where $l(\pi)$ denotes the length of the partition $\pi$, i.e., its number
of nonzero parts. The desired formula follows from the fact that $M(k,n)$
is the union of the sets $C(\pi)$ for partitions $\pi$ of $n$ of length $k$
(if a composition $c = (c_1, \dots, c_k)$ of $n$ is regarded as a map $c
\colon \range1k \to \range1n$ with $c(1) + \dots + c(k) = n$).
\end{proof}
\begin{Theorem} \label{thm:t}
The number $t(n)$ of unlabelled transitive relations on $n$ points is given
by
\begin{equation}
t(n) = \sum_{k=1}^n \sum_{H \in \RR_k} \mu_k(H)\, \# M'(k, n)/H,
\end{equation}
where $M'(k, n)$ is the set of maps $\{f \colon \range1k \to \{-1\} \cup
\range1n \mid \Size{f(1)} + \dots + \Size{f(k)} = n\}$.
\end{Theorem}
\begin{proof}
We argue along the same lines as in the proof of Theorem~\ref{thm:q},
taking the subsets $Y$ of irreflexive points into account.
Let $X = \range1n$ and let $G = \Sym(X)$.
Denote by $\Lambda_s(X)$ the set of all
augmented partitions $A$ of $X$ with $\Size{A \cap X} = s$.
The map $h \colon \TT(X) \to
\bigcup_{s \geq 0} \Lambda_s(X)$ which associates to each transitive
relation $R \in \TT(X)$ the augmented partition $X/\!/{\equiv_R} \in
\Lambda_s(X)$ induced by its symmetric core $\equiv_R$ on $X$ is a $G$-map.
Moreover, $G$ acts on $\Lambda_s(X)$ for every $s \geq 0$. Hence, by
Lemma~\ref{la:1},
\begin{equation}
\# \TT(X)/G = \sum_{s \geq 0} \sum_{K.G \in \Lambda_s(X)/G} h^{-1}(K)/G_K.
\end{equation}
Now let $K = L \cup Y$, where $Y \subseteq X$ is a subset of size $s$, and
$L = \{L_1, \dots, L_{k-s}\} \in \Lambda(X \setminus Y)$ is a partition of
$X\setminus Y$ with $k - s$ parts. Then the stabilizer $G_K$ contains a
normal subgroup $N = \Sym(L_1) \times \dots \times \Sym(L_k)$ which lies in
the kernel of the $G_K$-action on $h^{-1}(K)$. Let $H \leq \Sym(K)$ be the
group of permutations of $K$ induced by $G_K$, i.e., $H = \{ \bar{\alpha}:
K \to K \mid \alpha \in G_K\}$ where $L_i.\bar{\alpha} = L_i.\alpha$ for
all $L_i \in L$ and $x.\bar{\alpha} = x.\alpha$ for all $x \in Y$. Then
$G_K/N \cong H$ and
\begin{equation}
\# h^{-1}(K)/G_K = \# h^{-1}(K)/H = \# \PP(K)/H,
\end{equation}
since the set $\PP(K)$ of partial orders on $K$ is $H$-equivalent to
$h^{-1}(K)$. Now the map $K \to \range1k$ defined by $L_i \mapsto i$ and
$x_j \mapsto j$, where $Y = \{x_{k-s+1}, \dots, x_k\}$, translates $\PP(K)$
into $\PP(k)$ and $H$ into a subgroup $\tilde{H}$ of $\Sym(k)$.
Let us call \emph{signed composition} of $n$ a sequence $c = (c_1, \dots,
c_k)$ of nonzero integers $c_i \in {\Z \setminus \{0\}}$ such that
$\Size{c_1} + \dots + \Size{c_k} = n$. The \emph{positive shape} of the
signed composition $c = (c_1, \dots, c_k)$ is the partition $\pi$ given by
the sorted list of the nonnegative entries $c_i > 0$.
Then $\tilde{H}$ is the stabilizer of the signed composition $c =
(\Size{L_1}, \dots, \Size{L_{k-s}}, -1, \dots, -1)$ of $n$ with $s$ entries
$-1$ in the action of $\Sym(k)$ on all signed compositions of length $k$.
For a partition $\pi$ of $n-s$ let $C_s(\pi)$ be the set of all signed
compositions of $n$ with $s$ entries $-1$ that have positive shape $\pi$.
Note that, if $\pi$ is the positive shape of $c$ then $C_s(\pi) =
c.\Sym(k)$. Hence applying Lemma~\ref{la:2} twice yields
\begin{equation}
\# \PP(L)/H = \# \PP(k)/\tilde{H}
= \# (\PP(k) \times C(\pi)) / \Sym(k) %\\&
%= \sum_{P.\Sym(k) \in \PP(k)/\Sym(k)} \# C(\pi)/\Aut(P)
= \sum_{U \in \RR_k} \mu_k(U)\; \# C(\pi)/U,
\end{equation}
since $\mu_k(U)$ is the multiplicity of $U$ as stabilizer of a
$\Sym(k)$-orbit on $\PP(k)$.
Finally, the map which associates to every augmented partition $K = L \cup
Y \in \Lambda_s(X)$ the partition $[\Size{L_1}, \dots, \Size{L_{k-s}}]$ of
$n - s$ given by the sizes of the parts of $L= \{L_1, \dots, L_{k-s}\}$ is
a bijection between $\Lambda_s(X)/G$ and $\Pi(n-s)$. Thus
\begin{equation}
\# \TT(X)/G = \sum_{s \geq 0} \sum_{\pi \in \Pi(n-s)} \sum_{U}
\mu_{l(\pi)+s}(U)\; \#C_s(\pi)/U.
%= \sum_{k=1}^n \sum_{U \in \RR_k} \mu_k(U) \# M'(k, n)/U,
\end{equation}
where the inner sum is over all $U \in \RR_k$ for $k = l(\pi) + s$.
Summing over $k$ and the fact that $M'(k,n)$ is the union of all sets
$C_s(\pi)$ for $s \geq 0$ and partitions $\pi$ of $n-s$ of length $k - s$
yield the desired formula.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results.} \label{sec:results}
An implementation in \textsf{GAP} \cite{GAP} of the algorithm for the
enumeration of all types of partial orders as described in \cite{Heitzig00}
was used to enumerate the partial orders on up to $12$ points and to
determine their automorphism groups. In difficult cases Brendan McKay's
\textsf{nauty} \cite{nauty} was used for the computation of the automorphism
group. This program is accessible from within \textsf{GAP} through Leonard
Soicher's \textsf{GRAPE} \cite{grape} package. The results of the
enumeration process were recorded in a table, listing for every conjugacy
class of subgroups of $\Sym(n)$ how often it occurs as a stabilizer of an
(unlabelled) partial order on $n$ points. After determining the numbers of
orbits of the groups occurring in the list on the various domains,
Theorems~\ref{thm:s}, \ref{thm:q}, and \ref{thm:t} have been used to
calculate the sequences $s(n)$, $q(n)$, and $t(n)$. The tables of subgroups
of $\Sym(n)$ with their multiplicities as stabilizers of partial orders are
available from the author on request.
\begin{table} [htbp]
\begin{center}
\arraycolsep12pt
$\begin{array}{r|r|rrr} \hline
& \text{partial orders}
& \text{quasi-orders}
& \text{soft orders}
& \llap{\text{transitive relations}}
\\
n & p(n\rlap{)} & q(n\rlap{)} & s(n\rlap{)} & t(n\rlap{)} \\ \hline
0 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 2 & 2 \\
2 & 2 & 3 & 7 & 8 \\
3 & 5 & 9 & 32 & 39 \\
4 & 16 & 33 & 192 & 242 \\
5 & 63 & 139 & 1\>490 & 1\>895 \\
6 & 318 & 718 & 15\>067 & 19\>051 \\
7 & 2\>045 & 4\>535 & 198\>296 & 246\>895 \\
8 & 16\>999 & 35\>979 & 3\>398\>105 & 4\>145\>108 \\
9 & 183\>231 & 363\>083 & 75\>734\>592 & 90\>325\>655 \\
10 & 2\>567\>284 & 4\>717\>687 & 2\>191\>591\>226 & 2\>555\>630\>036 \\
11 & 46\>749\>427 & 79\>501\>654 & 82\>178\>300\>654 & 93\>810\>648\>902 \\
12 & 1\>104\>891\>746 &
1\>744\>252\>509 &
3\>984\>499\>220\>967 &
4\>461\>086\>120\>602 \\
\hline
\end{array}$
\end{center}
\caption{Numbers of unlabelled kinds of transitive relations.}\label{tab:trans}
\end{table}
Table~\ref{tab:trans} shows the numbers $q(n)$, $s(n)$, and $t(n)$ for $n = 0,
1, \dots, 12$. The additional column with the numbers $p(n)$ of partial
orders on $n$ points allows comparisons.
In practice, out of the many conjugacy classes of subgroups of $\Sym(n)$
(sequence \seqnum{A000638}) only very few do actually occur as automorphism
groups of partial orders (sequence \seqnum{A091070}). For comparison,
Table~\ref{tab:subgroups} also lists the number of conjugacy classes of
$\Sym(n)$ that occur as normalizers of a subgroup (sequence
\seqnum{A091071}). (See \cite{s12sub} for a detailed list of subgroups of
$\Sym(12)$.)
\begin{table}[htbp]
\begin{center}
$\begin{array}{lrrrrrrrrrrrr} \hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline
\text{classes of subgroups} &
1 & 2 & 4 & 11 & 19 & 56 & 96 & 296 & 554 & 1593 & 3094 & 10723 \\
\text{automorphism groups} &
1 & 2 & 3 & 6 & 8 & 16 & 21 & 41 & 57 & 103 & 140 & 276 \\
\text{normalizers} &
1 & 1 & 2 & 4 & 5 & 12 & 19 & 42 & 72 & 127 & 196 & 500 \\ \hline
\end{array}$
\end{center}
\caption{Numbers of Subgroups.} \label{tab:subgroups}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding Remarks and Questions.}
The enumeration of all the partial orders on $n$ points and their
automorphism groups takes a considerable amount of time. Due to huge numbers
of partial orders and the quick exponential growth of these numbers, it will
be difficult to calculate many more terms of the sequences $s(n)$, $q(n)$,
and $t(n)$ using this method. On the other hand, the number of automorphism
groups that occur is tiny by comparison. It might be interesting to approach
the problem of counting partial orders from that side: Is it possible to
characterize the subgroups of $\Sym(n)$ that occur as automorphism groups of
partial orders? Is it possible to enumerate partial orders with a given
automorphism group more efficiently?
\bigskip\bigskip\noindent
\textbf{Acknowledgments.} I am grateful to Jerome Sheahan for explaining
the statistical connection and to Britta Wienand for useful comments.
\bigskip\noindent
\textbf{Note added in proof.} I have learned from Brendan McKay that in
unpublished work in 2001, using a modification of their
program~\cite{Brinkmann02}, he and Brinkmann have obtained the numbers $q(n)$
for $n \leq 16$ and the numbers $s(n)$, $t(n)$ for $n \leq 15$; their numbers
are consistent with the numbers in Table~\ref{tab:trans}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
\href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}
\bibitem{Lygeros}
R.~Bayon, N.~Lygeros, and J.-S. Sereni, \emph{Enumeration of fixed effects and
mixed models}, \url{http://igd.univ-lyon1.fr/home/lygeros/models.html}.
\bibitem{Brinkmann02}
Gunnar Brinkmann and Brendan~D. McKay, \emph{Posets on up to 16 points}, Order
\textbf{19} (2002), no.~2, 147--179. \MR{2003e:05002}
\bibitem{GKP}
Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik, \emph{Concrete
mathematics}, Addison-Wesley Publishing Company Advanced Book Program,
Reading, MA, 1989, A foundation for computer science. \MR{91f:00001}
\bibitem{HararyPalmer}
Frank Harary and Edgar~M. Palmer, \emph{Graphical enumeration}, Academic Press,
New York, 1973. \MR{50 \#9682}
\bibitem{Heitzig00}
Jobst Heitzig and J{\"u}rgen Reinhold, \emph{The number of unlabeled orders on
fourteen elements}, Order \textbf{17} (2000), no.~4, 333--341 (2001).
\MR{2002a:06001}
\bibitem{Klaska1997}
Ji{\v{r}\'\i} Kla{\v{s}}ka, \emph{Transitivity and partial order}, Math. Bohem.
\textbf{122} (1997), no.~1, 75--82. \MR{98c:05006}
\bibitem{nauty}
Brendan~D. McKay, \emph{{nauty} user's guide (version 1.5), technical report
tr-cs-90-02}, Australian National University, Computer Science Department,
ANU, 1990, Home page: \url{http://cs.anu.edu.au/people/bdm/nauty}.
\bibitem{Oberschelp}
Walter Oberschelp, \emph{Kombinatorische {A}nzahlbestimmungen in {R}elationen},
Math. Ann. \textbf{174} (1967), 53--78. \MR{36 \#1342}
\bibitem{s12sub}
G{\"o}tz Pfeiffer, \emph{The subgroups of {$S_{12}$}},
\url{http://schmidt.nuigalway.ie/subgroups}, 2003, 597 pages.
\bibitem{GAP}
Martin Sch{\accent127 o}nert et~al., \emph{{GAP} -- {Groups}, {Algorithms}, and
{Programming}}, Lehrstuhl D f{\accent127 u}r Mathematik, Rheinisch
Westf{\accent127 a}lische Technische Hoch\-schule, Aachen, Germany, fifth
ed., 1995, Home page: \url{http://www.gap-system.org}.
\bibitem{oeis}
N.~J.~A. Sloane, \emph{The on-line encyclopedia of integer sequences},
published electronically at
\url{http://www.research.att.com/~njas/sequences/}, 2003.
\bibitem{grape}
Leonard~H. Soicher, \emph{{GRAPE}: a system for computing with graphs and
groups}, Proceedings of the 1991 DIMACS Workshop on Groups and Computation
(L.~Finkelstein and B.~Kantor, eds.), DIMACS Series in Discrete Mathematics
and Theoretical Computer Science, vol.~11, American Mathematical Society,
1993, Home page: \url{http://www.gap-system.org/Share/grape.html}.,
pp.~287--291.
\bibitem{Taylor1981}
W.~H. Taylor and H.~G Hilton, \emph{A structure diagram symbolization for
analysis of variance}, The American Statistician \textbf{35} (1981), 85--93.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 06A07.
\noindent \emph{Keywords:}
binary relation,
partial order,
quasi-order,
soft order,
transitive relation,
symmetric group,
group action,
finite topology,
automorphism group,
enumeration.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000027},
\seqnum{A000041},
\seqnum{A000070},
\seqnum{A000079},
\seqnum{A000088},
\seqnum{A000110},
\seqnum{A000112},
\seqnum{A000273},
\seqnum{A000595},
\seqnum{A000638},
\seqnum{A000666},
\seqnum{A000798},
\seqnum{A001035},
\seqnum{A001174},
\seqnum{A001930},
\seqnum{A002416},
\seqnum{A006125},
\seqnum{A006905},
\seqnum{A047656},
\seqnum{A053763},
\seqnum{A079265},
\seqnum{A083667},
\seqnum{A083670},
\seqnum{A091070},
\seqnum{A091071}
\seqnum{A091073},
and \seqnum{A091566}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received January 22 2004;
revised version received July 9 2004.
Published in {\it Journal of Integer Sequences}, August 2 2004.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}