\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}