<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[usenames]{color}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts,amssymb,latexsym,enumerate,theorem}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}





\long\global\def\C#1\F{{}}
\C----------------------------------
Revised version: October 22, 2003.
----------------------------------\F

\C +++ MACROS +++ \F
\newcommand{\one}{\textrm{1\hspace{-.5ex}l}}
\newcommand{\BBB}{\mathcal{B}{}}
\newcommand{\SSS}{\mathcal{S}{}}
\newcommand{\WWW}{\mathcal{W}{}}
\newcommand{\QED}{\mbox{}\nolinebreak\hfill\rule{2mm}{2mm}\medbreak\par}
\C +++ THEOREM(S) DEFINITIONS +++ \F
\theoremstyle{plain} \theoremheaderfont{\normalfont\bfseries}
{\theorembodyfont{\normalfont\slshape}
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}}
{\theorembodyfont{\normalfont}
\newtheorem{example}[theorem]{Example}}
\C +++========================+++ \F

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Counting Biorders
}
\vskip 1cm
\large
Julie Christophe\footnote{J.~C. is a Fellow of the Fonds pour
la Formation \`a la Recherche dans l'Industrie et dans
l'Agriculture.},
Jean-Paul Doignon\footnote{Corresponding author.}, and
Samuel Fiorini\footnote{S.~F. is supported by a Fellowship of the
Belgian American Educational Foundation.} \\
Universit\'e Libre de Bruxelles\\
D\'epartement de Math\'ematique, c.p.~216\\
Bd du Triomphe\\
B-1050 Bruxelles\\
Belgium\\
\href{mailto:juchrist@ulb.ac.be}{\tt juchrist@ulb.ac.be} \\
\href{mailto:doignon@ulb.ac.be}{\tt doignon@ulb.ac.be} \\
\href{mailto:sfiorini@ulb.ac.be}{\tt sfiorini@ulb.ac.be} \\
\end{center}

\vskip .2 in
\begin{abstract}
Biorders were introduced first as Guttman scales and then as
Ferrers relations.  They are now well recognized in combinatorics
and its applications.  However, it seems that no procedure besides
plain enumeration was made available for obtaining the number of
biorders from an $m$-element set to an $n$-element set.  We
establish first a double-recurrence formula for computing this
number, and then two explicit formulas involving Stirling numbers
of the second kind.  Our methods do not seem to extend to other,
similar structures.  For instance, interval orders on a finite set
are exactly the irreflexive biorders on that set.  To our
knowledge, no direct formula is available for deriving their
number.
\end{abstract}

\C==========================\F
\section{Introduction}
\label{Introduction}
Throughout the text, $X$ and $Y$ denote finite sets of respective
cardinalities $m$ and $n$. A \emph{biorder} from $X$ to $Y$ is
any relation from $X$ to $Y$ that admits a step-like
tableau, meaning: there exists some ordering $x_1$, $x_2$, \dots,
$x_m$ of the elements in $X$ and some ordering $y_1$, $y_2$, \dots,
$y_n$ of the elements in $Y$ such that the corresponding (boolean)
tableau of the relation has its $0$'s separated from its $1$'s by
a staircase, as in the following example:
\newcommand{\hor}{\rule [1mm]{3mm}{0.2mm}}
\newcommand{\ver}{\rule [0mm]{0.2mm}{3mm}}
\begin{eqnarray}
\begin{array}{rcccccccccccccc}
&amp;&amp; y_1 &amp;&amp; y_2 &amp;&amp; y_3 &amp;&amp; y_4 &amp;&amp; y_5 &amp;&amp; y_6 &amp;&amp; y_7\\[4mm]
x_1\quad &amp;\ver&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1\\\\
x_2 \quad&amp;\ver&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1\\
&amp;&amp;\hor&amp;&amp;\hor\\
x_3\quad &amp;&amp; 0 &amp;&amp; 0 &amp; \ver &amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1\\
&amp;&amp;&amp;&amp;&amp;&amp;\hor\\
x_4\quad &amp;&amp; 0 &amp;&amp; 0 &amp;&amp; 0 &amp;\ver&amp; 1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1 \\
\\
x_5\quad &amp;&amp; 0 &amp;&amp; 0 &amp;&amp; 0 &amp;\ver&amp;  1 &amp;&amp; 1 &amp;&amp; 1 &amp;&amp; 1\\
&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;\hor&amp;&amp;\hor&amp;&amp;\hor&amp;&amp;\hor
\end{array}
\end{eqnarray}
Also, a relation $R$ from $X$ to $Y$ is a biorder if and only if it
satisfies any of the following equivalent conditions:
\begin{enumerate}
\item for all $w,x\in X$ and $y,z\in Y$: 
\begin{eqnarray}
(wRy\textrm{ and } xRz) &amp;\textrm{ implies }&amp; (wRz
\textrm{ or } xRy);
\end{eqnarray}
\item all subsets $R(x)=\{y\in Y \,\vert\, xRy\}$, for $x\in X$,
form a chain of subsets of $Y$ (repetitions being allowed);
\item all subsets $R^{-1}(y)=\{x\in X \,\vert\, xRy\}$, for $y\in
Y$, form a chain of subsets of $X$;
\item no tableau for $R$ contains a subtableau of the form
\begin{eqnarray}
\left(\begin{array}{cc}
0 &amp; 1\\ 1 &amp; 0
\end{array}
\right)
\qquad\mathrm{or}\qquad
\left(\begin{array}{cc}
1 &amp; 0\\ 0 &amp; 1
\end{array}
\right).
\end{eqnarray}
\end{enumerate}

These simple conditions, and several other ones, were established
when biorders were first introduced in psychology as `scales' by
Guttman \cite{Guttman44}, and then in mathematics as `Ferrers
relations' by Riguet \cite{Riguet51}.  For a survey of the early
history of biorders, see Monjardet \cite{Monjardet1978}. 
Besides their use in social sciences, biorders have proved useful 
in a variety of situations.  For instance, they come as a
convenient, technical tool for Yannakakis \cite{Yannakakis1982}, or
they are used as the $1$-dimensional constituents in a
dimensional theory of relations by Cogis \cite{Cogis1982b} and
Doignon, Ducamp and Falmagne~\cite{DoignonDucampFalmagne84} (the
latter reference introduced the term `biorder').

Although biorders are by now well assimilated in some chapters of
combinatorics and its applications, it seems that no direct method
for counting biorders was ever published.  We will provide three
formulas for obtaining the number of biorders from an $m$-element
set to an  $n$-element set.  A first formula captures a
double-recurrence approach.  Then an explicit formula is
derived which relies on Stirling numbers of the second kind. 
Still another formula is established along another line
of reasoning, which also makes use of the same Stirling numbers. 

Our method does not seem to be applicable to related, similar
structures.  For instance (see, e.g., Fishburn \cite{Fishburn1985}
for these concepts), interval orders on a finite set $Z$ are
exactly the irreflexive biorders from $Z$ to $Z$, while semiorders
are the interval orders satisfying also for $x$, $y$, $z$, $t\in Z$
\begin{eqnarray}
\label{eq-so}
(xRy\textrm{ and } yRz) &amp;\textrm{ implies }&amp; (xRt
\textrm{ or } tRz).
\end{eqnarray}
Formulas for the number of semiorders on an $n$-element set are
given in Chandon, Lemaire and Pouget
\cite{ChandonLemairePouget1978} (see also Sequence A006531 in
the On-Line Encyclopedia of Integer Sequences~\cite{SloaneEIS}),
but apparently no explicit formula is known in the literature for
the similar number of interval orders. 

Notice that all counts mentioned so far are for labeled
structures.  As regards counting up to isomorphism, the case of
semiorders leads to the Catalan number $\frac1{n+1}{2n \choose n}$
(see \cite{Fishburn1985} or Sequence A000108~\cite{SloaneEIS}),
while a polynomial-time algorithm for computing the number of
isomorphism types of interval orders is due to Haxell, McDonald and
Thomason~\cite{HaxellMcDonaldThomason1987} (Sequence
A022493~\cite{SloaneEIS}).  On the other hand, the case of
biorders from $X$ to $Y$ is easy in case $X \cap Y =\varnothing$:
there are ${m+n\choose n}$ isomorphism types of biorders from an
$m$-element set $X$ to a disjoint $n$-element set $Y$.  To prove
this, we need only indicate how to count step-like
tableaus, and it suffices to point out that the separating staircase
is made of $m+n$ strokes, of which $m$ are vertical and $n$ are
horizontal.

\C===============================================================\F
\section{Double Recurrence}
\label{Double Recurrence}

Let us denote by $\BBB(m,n)$ the quantity we are interested
in, that is the number of biorders from the $m$-element set $X$ to
the $n$-element set $Y$.  
Assuming $X \cap Y=\varnothing$ does not set any restriction here,
because of the duplication construction of Doignon, Ducamp and
Falmagne~\cite{DoignonDucampFalmagne84}; the reader might find it
helpful to assume $X\cap Y=\varnothing$.  
The following proposition shows how to compute numbers $\BBB(m,n)$
by a double recurrence.

\begin{proposition} \label{dr}
For $m&gt;0$ and $n&gt;0$, we have
\begin{eqnarray}
\label{eqdr}
\BBB(m,n) &amp;=&amp; 
\sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose j}
\; {n \choose k} \; \BBB(j,k)
\end{eqnarray}
and
\begin{eqnarray}
\label{eqdr0}
\BBB(m,0) \;=\; \BBB(0,n) \;=\; 1,
\end{eqnarray}
together with
\begin{eqnarray}
\label{eqdr00}
\BBB(0,0) &amp;=&amp; 2.
\end{eqnarray}
\end{proposition}


\noindent\emph{Proof}. A tableau is said to be of Type~$0$
if it has a column of $0$'s, and of Type~$1$ if it has a row of
$1$'s.  Correspondingly, a biorder from $X$ to $Y$ is of Type~$0$
if at least one set $R^{-1}(y)$ is empty, where $y\in Y$;  denote by
$\BBB_0(m,n)$ the number of biorders of Type~$0$.  
Similarly, a biorder from $X$ to $Y$ is of Type~$1$ if $R(x)=Y$
holds for at least one element $x$ in $X$; denote by $\BBB_1(m,n)$
the number of such biorders.  Notice the equality
\begin{eqnarray}
\label{0t1}
\BBB_0(m,n) &amp;=&amp; \BBB_1(n,m),
\end{eqnarray}
which follows from the following two facts: first, taking the
complement of the converse of a biorder from $X$ to $Y$
always gives a biorder from $Y$ to $X$, second this operation
transforms a Type~$0$ tableau into a Type~$1$ tableau.

Moreover, from the definition of biorders, we get at once
\begin{eqnarray}
\label{0-1}
\BBB(m,n) &amp;=&amp; \BBB_0(m,n) + \BBB_1(m,n).
\end{eqnarray}

To obtain recurrence relations first for $\BBB_1(m,n)$ and then for
$\BBB(m,n)$, we now suppose $m&gt;0$ and $n&gt;0$ and fix some
orderings of $X$ and $Y$.  Thus any biorder (even, any relation) 
corresponds to exactly one tableau.
 
Any Type~$1$ biorder is univocally formed by (i)~selecting $j$
among the $m$ rows, for some $j$ with $0 \le j &lt; m$, (ii)~then
setting all entries in the $m-j$ other rows to $1$, and
(iii)~finally specifying some Type~$0$ tableau on the selected $j$
rows.  This shows
\begin{equation}
\label{1-1}
\BBB_1(m,n) \;=\; 
\sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_0(j,n)
\;=\; 
\sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_1(n,j).
\end{equation}

Now the following computations based on
Equations~(\ref{0t1})--(\ref{1-1}) give us Equation~(\ref{eqdr}) in
the statement:
\begin{eqnarray*}
\BBB(m,n) &amp;=&amp; \BBB_0(m,n) + \BBB_1(m,n)\\
&amp;=&amp; \BBB_1(n,m) + \BBB_1(m,n)\\
%
&amp;=&amp;\sum_{k=0}^{n-1} \;\;\;{n \choose k} \; \BBB_1(m,k) +
\sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_1(n,j)\\
%
&amp;=&amp;\sum_{k=0}^{n-1} {n \choose k}  \sum_{j=0}^{m-1}
{m \choose j} \BBB_0(j,k) + 
\sum_{j=0}^{m-1}  {m \choose j} \sum_{k=0}^{n-1} {n \choose k}  
\BBB_1(j,k)\\
%
&amp;=&amp; \sum_{j=0}^{m-1}\; \sum_{k=0}^{n-1} \;\;\;
{m \choose j} \; {n \choose k} \; \BBB(j,k).
\end{eqnarray*}

Finally, the values in Equations~(\ref{eqdr0})--(\ref{eqdr00}) are
chosen to generate the correct expressions $\BBB(m,1)=2^m$ and
$\BBB(1,n)=2^n$.
\QED

With a program implementing the formulas from
Equation~(\ref{eqdr}),  we computed the values of $\BBB(m,n)$ shown
in Table~1.  Notice $\BBB(m,n)=\BBB(n,m)$ (which holds because the
converse of a biorder is always a biorder).  The first two rows in
Table~1 are easily explained.  For $m=1$, we have
$\BBB(1,n)=2^n$.  For $m=2$, the tableaux of biorders are exactly
those tableaux not containing both a column $0 \atop 1$ and a
column $1 \atop 0$.  Hence their number satisfies $\BBB(2,n)=
2\cdot 3^n - 2 ^n$.

\begin{table}
\begin{center}
\halign{ $#$\quad&amp;&amp;\quad\hfil$#$\cr
m \backslash
n&amp;1&amp;2&amp;3&amp;4&amp;5&amp;6&amp;7&amp;8\cr
\noalign{\vskip3mm\hrule\vskip3mm}
1&amp;2&amp;4&amp;8&amp;16&amp;32&amp;64&amp;128&amp;256\cr
2&amp;&amp;14&amp;46&amp;146&amp;454&amp;1\,394&amp;4\,246&amp;12\,866\cr
3&amp;&amp;&amp;230&amp;1\,066&amp;4\,718&amp;20\,266&amp;85\,310&amp;354\,106\cr
4&amp;&amp;&amp;&amp;6\,902&amp;41\,506&amp;237\,686&amp;1\,315\,666&amp;
7\,107\,302\cr
5&amp;&amp;&amp;&amp;&amp;329\,462&amp;2\,441\,314&amp;17\,234\,438&amp;117\,437\,746\cr
6&amp;&amp;&amp;&amp;&amp;&amp;22\,934\,773&amp;
202\,229\,266&amp; 1\,701\,740\,006\cr}
\end{center}
\caption{Some values of $\BBB(m,n)$.}
\end{table}



\C=================================================================\F
\section{A First Explicit Formula}
\label{First Explicit}

Some hand computations exploiting the double-recurrence in
Proposition~\ref{eqdr} strongly suggest to write $\BBB(m,n)$ as a
weighted sum of $n$-th powers.  To identify the coefficients, we
use the Stirling numbers of the second kind, here denoted
as $\SSS(m,j)$ (see, e.g., \cite{GrahamKnuthPatashnik1989} where the
notation $\left\{m \atop j \right\}$ is used).  Remember that 
$\SSS(m,j)$, the number of ways of partitioning an $m$-element set
into $j$ classes, equals
\begin{eqnarray}
\label{eqst}
\SSS(m,j) &amp;=&amp; \frac{1}{j!}\;\sum_{i=1}^j (-1)^{j-i} \; {j
\choose i} \; i^m.
\end{eqnarray}
Here are some other properties of these numbers, for $m&gt;0$: 
\begin{eqnarray}
\SSS(m,j)&amp;=&amp;0 \qquad\mathrm{when~} j &lt; 1 \mathrm{~or~} m &lt; j,\\
\SSS(m,m)&amp;=&amp;\SSS(m,1)\;=\;1,
\end{eqnarray} 
and
\begin{eqnarray}
\label{eqStrec}
\SSS(m,u) &amp;=&amp; \SSS(m-1,u-1)+u\; \SSS(m-1,u).
\end{eqnarray}
We will also need (see \cite{GrahamKnuthPatashnik1989},
Equation~(6.17) and on page 264, the formula for $x^n$, with $x$
set to $1$): for $1 \le j \le m$,
\begin{eqnarray}
\label{eqSt}
\SSS(m,j) &amp;=&amp; \sum_{k=j}^m\;\;{m \choose k} \;
(-1)^{m-k} \; \SSS(k+1,j+1),
\end{eqnarray}
and for $m \ge 1$,
\begin{eqnarray}
1&amp;=&amp;\sum_{t=1}^{m} \;\; (-1)^{m+t} \; t! \;  \SSS(m,t)
\label{eqnew}.
\end{eqnarray}

\begin{proposition} \label{fe}
For $m&gt;0$ and $n\ge 0$, we have
\begin{eqnarray}
\label{eqfe}
\BBB(m,n) &amp;=&amp; 
\sum_{t=1}^{m}\;\; (-1)^{m+t}\; t! \; \SSS(m,t) \; (t+1)^n. 
\end{eqnarray}
\end{proposition}

\noindent\emph{Proof}. Setting for $m&gt;0$ and $m \ge t \ge 1$
\begin{eqnarray}
\label{eqb}
b_{m,t} &amp;=&amp;  (-1)^{m+t}\; t! \; \SSS(m,t),
\end{eqnarray}
and also for convenience $b_{m,m+1}=0$, 
we first record some properties of the numbers $b_{m,n}$:
\begin{eqnarray}
b_{m,1} &amp;=&amp; (-1)^{m+1};\label{eqA}\\
b_{m,m} &amp;=&amp; m!\;;\label{eqB}\\
b_{m,t} &amp;=&amp; \sum_{j=t-1}^{m-1} \;\;
{m \choose j} (b_{j,t-1}-b_{j,t}), \qquad \mathrm{for~} 1 &lt; t &lt;
m\label{eqC}.
\end{eqnarray}
Equation~(\ref{eqA}) follows from $\SSS(m,1)=1$, and
Equation~(\ref{eqB}) from $\SSS(m,m)=1$.  More computations are needed
for the next equation.  Starting from the right-hand side of
Equation~(\ref{eqC}), we have (in view of
Equations~(\ref{eqStrec}) and (\ref{eqSt}))
\begin{eqnarray*}
\lefteqn{\sum_{j=t-1}^{m-1} \;\;
{m \choose j} (b_{j,t-1}-b_{j,t})}\hspace{9mm}\\
&amp;=&amp;\sum_{j=t-1}^{m-1} \;\;
{m \choose j} (-1)^{j+t-1} (t-1)! \; \Big(\SSS(j,t-1)+t \;
\SSS(j,t)\Big)\\
&amp;=&amp;
(t-1)! \; (-1)^{t-1} \; \sum_{j=t-1}^{m-1}\;\; {m \choose j} \;
(-1)^j \; \SSS(j+1,t)\\
&amp;=&amp;
(t-1)! \; (-1)^{t-1} \; (-1)^m \; \big(\SSS(m,t-1)-\SSS(m+1,t)\big)\\
&amp;=&amp;
(-1)^{m+t} \; (t-1)!  \; t \; \SSS(m,t)\\
&amp;=&amp; b_{m,t}
\end{eqnarray*}
which establishes Equation~(\ref{eqC}). 

Next we establish by double recurrence on
$m&gt;0$ and $n\ge 0$ the equality in the thesis, rephrased as:
\begin{eqnarray}
\label{eqbb}
\BBB(m,n) &amp;=&amp; 
\sum_{t=1}^{m} b_{m,t}\; (t+1)^n. 
\end{eqnarray}
This equality holds for sure in case $m=1$ because of
$\BBB(1,n)=2^n$ and Equation~(\ref{eqA}); it also holds in case
$n=0$, in view of $\BBB(m,0)=1$ for $m\neq 0$
and Equation~(\ref{eqnew}).
 
Supposing now that the following equation holds for $1 \le j &lt; m$
and $0\le k &lt; n$
\begin{eqnarray}
\label{eqind}
\BBB(j,k) &amp;=&amp; 
\sum_{t=1}^{j} b_{j,t}\; (t+1)^k,
\end{eqnarray}
we proceed to infer Equation~(\ref{eqbb}).
After having inserted Equation~(\ref{eqind}) into
Equation~(\ref{eqdr}), we get successively
\begin{eqnarray*}
\lefteqn{\BBB(m,n) } \hspace{3mm}\\
&amp;=&amp;\sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose
j}
\; {n \choose k} \; \BBB(j,k)\\
%
&amp;=&amp; \BBB(0,0) 
+ 
\sum_{k=1}^{n-1} \; {n \choose k} \; \BBB(0,k) 
+
\sum_{j=1}^{m-1} \sum_{k=0}^{n-1} {m \choose j}
\; {n \choose k} \; \sum_{t=1}^{j} \;b_{j,t}\; (t+1)^k\\
%
&amp;=&amp; 2 + (2^n-2)
+
\sum_{j=1}^{m-1} \; {m \choose j} \;
\sum_{t=1}^{j} \; b_{j,t} \;
\sum_{k=0}^{n-1} \; {n \choose k} \; (t+1)^k\\
&amp;=&amp;
2^n 
+
\sum_{j=1}^{m-1} \; {m \choose j} 
\sum_{t=1}^{j} \; b_{j,t} (1+t+1)^n
-
\sum_{j=1}^{m-1}  {m \choose j} 
\sum_{t=1}^{j}\;
b_{j,t} (t+1)^n.
\end{eqnarray*}
Then replacing $t+1$ with $t$ in the second term, we have
\begin{eqnarray*}
\lefteqn{\BBB(m,n) }\hspace{1mm}\\
&amp;=&amp; 2^n 
+
\sum_{j=1}^{m-1} \; {m \choose j} \;
\sum_{t=2}^{j+1} \; b_{j,t-1} \; (t+1)^n
-
\sum_{j=1}^{m-1} \; {m \choose j} \; \sum_{t=1}^{j} \;\; b_{j,t}
(t+1)^n\\
%
%
%
&amp;=&amp;\left(1-\sum_{j=1}^{m-1} {m \choose j}\; b_{j,1} \right) 2^n
+
\sum_{j=1}^{m-1} \; {m \choose j} \;
\sum_{t=2}^{j+1} \; \left(b_{j,t-1}-b_{j,t}\right) \; (t+1)^n
\end{eqnarray*}
and using $b_{j,j+1}=0$
\begin{eqnarray*}
\lefteqn{\BBB(m,n) }\hspace{1mm}\\
%
%
&amp;=&amp;\left(1-\sum_{j=1}^{m-1} {m \choose j}\; (-1)^{j+1} \right)
2^n
+
\sum_{t=2}^{m} \; (t+1)^n\; \sum_{j=t-1}^{m-1} \;\; {m
\choose j} \; \left( b_{j,t-1}-b_{j,t}\right)\\
%
%
%
&amp;=&amp;(-1)^{m+1}\; 2^n\\
&amp;&amp;\qquad\qquad
+
\sum_{t=2}^{m-1} \; (t+1)^n\; \sum_{j=t-1}^{m-1} \;\; {m
\choose j} \; \left( b_{j,t-1}-b_{j,t}\right) 
\\&amp;&amp;\qquad\qquad\qquad\qquad
+ m\; b_{m-1,m-1} \; (m+1)^n.\end{eqnarray*}
Now Equations~(\ref{eqA}), (\ref{eqC}), (\ref{eqB}) lead to
\begin{eqnarray*}
\BBB(m,n) &amp;=&amp;
b_{m,1} 2^n
+
\sum_{t=2}^{m-1} \;\; b_{m,t} \; (t+1)^n 
+
b_{m,m}\; (m+1)^n
\end{eqnarray*}
which is Equation~(\ref{eqbb}). 
This completes the proof by recurrence.
\QED

Replacing the Stirling numbers in Equation~(\ref{eqfe}) with their
expressions from Equation~(\ref{eqst}), we derive the more explicit
formula
\begin{eqnarray}
\BBB(m,n) &amp;=&amp;
\sum_{i=1}^{m}\; (-1)^{m-i}\;\; i^m \; \sum_{t=i}^m  \; {t
\choose i} \; (t+1)^n. 
\end{eqnarray}

Another reformulation is obtained by introducing the number
$\WWW(m,k)=k!\;\SSS(m,k)$ of weak orders with $k$ classes on an
$m$-element set:
\begin{eqnarray}
\BBB(m,n) &amp;=&amp;
\sum_{t=1}^{m}\;\; (-1)^{m+t}\; \WWW(m,t) \; (t+1)^n. 
\end{eqnarray}

All of these formulas for $\BBB(m,n)$ are alternating sums.  We now
turn to another way of counting, which will provide us with a sum of
positive terms.

 
\C===============================================================\F
\section{A Second Explicit Formula}
\label{Second Explicit}

In view of the properties collected in the Introduction, any
biorder $B$ from $X$ to $Y$ determines a weak order $B_X$ on
$X$ and a weak order $B_Y$ on $Y$, defined through
\begin{eqnarray}
x \;B_X\; x' \iff B(x) \subseteq B(x'), \quad\mathrm{ and }\quad
y \;B_Y\; y' \iff B^{-1}(y) \subseteq B^{-1}(y').
\end{eqnarray}

\begin{proposition} \label{prop-sf}
Given a biorder $B$ from $X$ to $Y$, the two weak
orders $B_X$ and $B_Y$ have their numbers of equivalence classes
differing by at most one.  Conversely, any two weak orders on
respectively $X$ and $Y$ which have the same number of equivalence
classes derive in this way from exactly two biorders from $X$ to
$Y$.  Also, if two weak orders on
respectively $X$ and $Y$ have their numbers of equivalence
classes differing by $1$, then they derive from exactly one
biorder from $X$ to $Y$. 
\end{proposition}

\noindent\emph{Proof}.
All assertions can be easily checked by considering a step-like
tableau for the (given or to-be-constructed) biorder $B$.
\QED

We now derive a second explicit formula for the number of biorders
from $X$ to $Y$, which in case $|X|=|Y|$ was first obtained by
Destr\'ee \cite{Destree1996}.

\begin{proposition} \label{prop-sfbis}
The number $\BBB(m,n)$ of biorders from $X$ to $Y$, where $|X|=m$
and $|Y|=n$, equals
\begin{eqnarray}
\BBB(m,n) &amp;=&amp; \sum_{k=1}^m k!\; (k-1)! \; \SSS(m,k) \; \big(\SSS(n+1,k)
+ k\, \SSS(n+1,k+1)\big).\label{eq-sf}
\end{eqnarray}
\end{proposition}

Remark that, contrary to Equation~(\ref{eqfe}), we have here a sum
of positive terms.  On the other hand, there are more summations
here, because each Stirling number requires one.

\vspace{2mm}

\noindent\emph{Proof}.
&gt;From Proposition~\ref{prop-sf}, we derive
\begin{eqnarray*}
\lefteqn{\BBB(m,n) \quad=}\\
&amp;&amp;\sum_{k=1}^m k!\, \SSS(m,k) \, \big( (k-1)! \, 
\SSS(n,k-1) + 2 \, k!\, \SSS(n,k) + (k+1)!\, \SSS(n,k+1)\big).
\end{eqnarray*}
Applying Equation~(\ref{eqStrec}), we get Equation~(\ref{eq-sf}).
\QED

In the particular case $m=n$, we have \cite{Destree1996}
\begin{eqnarray}
\BBB(m,m) &amp;=&amp; 2\;\sum_{k=1}^m \; (k!)^2\;  \SSS(m,k) \; \SSS(m+1,k+1).
\end{eqnarray}

Returning to the general case, we conclude that the number of
biorders both equals either side of
\begin{eqnarray}
\lefteqn{
\sum_{t=1}^{m}\;\; (-1)^{m+t}\; t! \; \SSS(m,t) \; (t+1)^n
\quad=}\nonumber\\ &amp;&amp;\sum_{k=1}^m k!\; (k-1)! \; \SSS(m,k) \;
\big(\SSS(n+1,k) + k\, \SSS(n+1,k+1)\big)
\label{eqf}
\end{eqnarray}
and is the solution to the double recurrence, for $m&gt;0$ and $n&gt;0$,
\begin{eqnarray}
\BBB(m,n) &amp;=&amp; 
\sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose j}
\; {n \choose k} \; \BBB(j,k),
\label{eqff}
\end{eqnarray}
with initial conditions
\begin{eqnarray}
\BBB(m,0) = \BBB(0,n) = 1
&amp;\mathrm{and}&amp;
\BBB(0,0) = 2.
\end{eqnarray}

\C===============================\F
%\bibliographystyle{plain}
%\bibliography{jpd}

\begin{thebibliography}{10}

\bibitem{ChandonLemairePouget1978}
J.-L.~Chandon, J.~Lemaire, and J.~Pouget,
\newblock D\'enombrement des quasi-ordres sur un ensemble fini,
\newblock {\em Math.\ Sci.\ Humaines} {\bf 62} (1978),
61--80.

\bibitem{Cogis1982b}
O.~Cogis,
\newblock On the {F}errers dimension of a digraph,
\newblock {\em Discrete Math.} {\bf 38} (1982), 47--52.

\bibitem{Destree1996}
L.~{Destr{\'e}e},
\newblock Probl{\`e}mes algorithmiques sur les biordres et mod{\`e}les
  relationnels apparent{\'e}s,
\newblock Master's thesis, Universit{\'e} Libre de Bruxelles, D{\'e}partement
  d'Informatique, Brussels, Belgium, 1996.

\bibitem{DoignonDucampFalmagne84}
J.-P.~Doignon, A.~Ducamp, and J.-Cl.~Falmagne,
\newblock On realizable biorders and the biorder dimension of a relation,
\newblock {\em J.\ Math.\ Psych.} {\bf 28} (1984), 73--109.

\bibitem{Fishburn1985}
P.C.~Fishburn,
\newblock {\em Interval Orders and Interval Graphs},
\newblock Wiley, 1985.

\bibitem{GrahamKnuthPatashnik1989}
R.L.~Graham, D.E.~Knuth, and O.~Patashnik,
\newblock {\em Concrete Mathematics},
\newblock Addison Wesley, 1986.

\bibitem{Guttman44}
L.~Guttman,
\newblock A basis for scaling quantitative data,
\newblock {\em American Sociological Review} {\bf 9} (1944), 139--150.

\bibitem{HaxellMcDonaldThomason1987}
P.E.~Haxell, J.J.~McDonald, and S.K.~Thomason,
\newblock Counting interval orders,
\newblock {\em Order} {\bf 4} (1987), 269--272.

\bibitem{Monjardet1978}
B.~Monjardet,
\newblock Axiomatiques et propri\'et\'es des quasi-ordres,
\newblock {\em Math.\ Sci.\ Humaines}
{\bf  63} (1978), 51--82.

\bibitem{Riguet51}
J.~Riguet,
\newblock Les relations de {F}errers,
\newblock {\em C.\ R.\ Acad.\ Sci.\ Paris}
{\bf 232} (1951), 1729--1730.

\bibitem{SloaneEIS}
N.J.A.~Sloane,
\newblock {\em The On-line Encyclopedia of Integer Sequences},
\newblock {P}ublished electronically at
  http://www.research.att.com/$\sim$njas/sequences/, 2003.

\bibitem{Yannakakis1982}
M.~Yannakakis,
\newblock The complexity of the partial order dimension problem,
\newblock {\em SIAM J.\ Algebraic Discrete Methods}
{\bf 3} (1982), 351--358.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15 ; Secondary 06A06.

\noindent \emph{Keywords: }
biorder, Stirling number of the second kind.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A006531},
\seqnum{A000108},
\seqnum{A022493}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 17 2003;
revised version received October 27 2003.
Published in {\it Journal of Integer Sequences}, December 12 2003.

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