<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 &gt; 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 &gt; 0$ points is the identity
relation; the only irreflexive transitive relation on $n &gt; 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 &amp;$\#$ Labeled Relations &amp; \multicolumn{2}{l}{$\#$ Unlabeled Relations on $n$ points} \\ \hline
  (none) &amp; $\strut 2^{n^2} =\ $\seqnum{A002416}$(n)$ &amp; \seqnum{A000595}$(n)$ &amp; all relations \\
 R\S\T\A &amp; $4^{\binom{n}2} =\ $\seqnum{A053763}$(n)$ &amp; \seqnum{A000273}$(n)$ &amp; reflexive \\
\R S\T\A &amp; $2^{\binom{n+1}2} =\ $\seqnum{A006125}$(n{+}1)$ &amp; \seqnum{A000666}$(n)$ &amp; symmetric \\
\R\S T\A &amp; $T(n) =\ $\seqnum{A006905}$(n)$ &amp; $t(n) =\ $\seqnum{A091073}$(n)$ &amp; transitive \\
\R\S\T A &amp; $2^n 3^{\binom{n}2} =\ $\seqnum{A083667}$(n)$ &amp; \seqnum{A083670}$(n)$ &amp; antisymmetric \\
  RS\T\A &amp; $2^{\binom{n}2} =\ $\seqnum{A006125}$(n)$ &amp; \seqnum{A000088}$(n)$ &amp; simple graphs \\
 R\S T\A &amp; $Q(n) =\ $\seqnum{A000798}$(n)$ &amp; $q(n) =\ $\seqnum{A001930}$(n)$ &amp; quasi-orders \\
 R\S\T A &amp; $3^{\binom{n}2} =\ $\seqnum{A047656}$(n)$ &amp; \seqnum{A001174}$(n)$ &amp;  \\
 \R ST\A &amp; $E(n{+}1) =\ $\seqnum{A000110}$(n{+}1)$ &amp; $e(0) + \dots + e(n) =\ $\rlap{\seqnum{A000070}$(n)$} &amp;  \\
 \R\S TA &amp; $S(n) =\ $\seqnum{A091566}$(n)$ &amp; $s(n) =\ $\seqnum{A079265}$(n)$ &amp; soft orders \\
   RST\A &amp; $E(n) =\ $\seqnum{A000110}$(n)$ &amp; $e(n) =\ $\seqnum{A000041}$(n)$ &amp; equivalences \\
  R\S TA &amp; $P(n) =\ $\seqnum{A001035}$(n)$ &amp; $p(n) =\ $\seqnum{A000112}$(n)$ &amp; partial orders \\
  \R STA &amp; $2^n =\ $\seqnum{A000079}$(n)$ &amp; $n{+}1 =\ $\seqnum{A000027}$(n{+}1)$ &amp; 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) &amp;= \sum_{H \in \RR_n} \mu_n(H), &amp; 
  P(n) &amp;= \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) %\\&amp;
%= \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 &gt; 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) %\\&amp;
   %= \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
&amp; \text{partial orders} 
&amp; \text{quasi-orders}
&amp; \text{soft orders}
&amp; \llap{\text{transitive relations}}
\\
 n &amp;  p(n\rlap{)} &amp; q(n\rlap{)} &amp; s(n\rlap{)} &amp; t(n\rlap{)} \\ \hline
 0 &amp; 1 &amp;        1 &amp;             1 &amp;                1 \\            
 1 &amp; 1 &amp;         1 &amp;             2 &amp;                2 \\           
 2 &amp; 2 &amp;         3 &amp;             7 &amp;                8 \\           
 3 &amp; 5 &amp;          9 &amp;            32 &amp;               39 \\          
 4 &amp; 16 &amp;         33 &amp;           192 &amp;              242 \\         
 5 &amp; 63 &amp;         139 &amp;          1\&gt;490 &amp;             1\&gt;895 \\        
 6 &amp; 318 &amp;         718 &amp;         15\&gt;067 &amp;            19\&gt;051 \\       
 7 &amp; 2\&gt;045 &amp;        4\&gt;535 &amp;        198\&gt;296 &amp;           246\&gt;895 \\      
 8 &amp; 16\&gt;999 &amp;       35\&gt;979 &amp;       3\&gt;398\&gt;105 &amp;          4\&gt;145\&gt;108 \\     
 9  &amp; 183\&gt;231 &amp;      363\&gt;083 &amp;      75\&gt;734\&gt;592 &amp;         90\&gt;325\&gt;655 \\    
 10 &amp; 2\&gt;567\&gt;284 &amp;     4\&gt;717\&gt;687 &amp;     2\&gt;191\&gt;591\&gt;226 &amp;       2\&gt;555\&gt;630\&gt;036 \\  
 11 &amp; 46\&gt;749\&gt;427 &amp;    79\&gt;501\&gt;654 &amp;    82\&gt;178\&gt;300\&gt;654 &amp;      93\&gt;810\&gt;648\&gt;902 \\
 12 &amp; 1\&gt;104\&gt;891\&gt;746 &amp;   
1\&gt;744\&gt;252\&gt;509 &amp;
3\&gt;984\&gt;499\&gt;220\&gt;967 &amp;
4\&gt;461\&gt;086\&gt;120\&gt;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 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 \\ \hline
\text{classes of subgroups} &amp;
1 &amp; 2 &amp; 4 &amp; 11 &amp; 19 &amp; 56 &amp; 96 &amp; 296 &amp; 554 &amp; 1593 &amp; 3094 &amp; 10723 \\
\text{automorphism groups} &amp;
1 &amp; 2 &amp; 3 &amp; 6 &amp; 8 &amp; 16 &amp; 21 &amp; 41 &amp; 57 &amp; 103 &amp; 140 &amp; 276 \\
\text{normalizers} &amp;
1 &amp; 1 &amp; 2 &amp; 4 &amp; 5 &amp; 12 &amp; 19 &amp; 42 &amp; 72 &amp; 127 &amp; 196 &amp; 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}
</pre></body></html>